线性dp:DP3 跳台阶扩展问题

69 阅读 0 评论 46 点赞

我是靠谱客的博主害怕冬天，最近开发中收集的这篇文章主要介绍线性dp:DP3 跳台阶扩展问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

输入描述：

本题输入仅一行，即一个整数 n

输出描述：

输出跳上 n 级台阶的跳法

思路：
f(n)=f(n-1)+.....f(1)
f(n-1) = f(n-2) + .....f(1)

化简可得：f(n) = 2* f(n-1)
即：f(n)/f(n-1) = 2，等比数列，公比是2.

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	int n = 0;
	cin >> n;
/*
	vector<int> dp(n + 1);
	int sum = 0;
	for (int i = 0; i <= n; ++i)
	{
		if (i == 0 || i == 1)
			dp[i] = 1;
		else
		{
			dp[i] = sum;
		}
		sum += dp[i];
	}
	cout << dp[n];
*/
	int ans = 1;
	while (n-->1)
	{
		ans = ans << 1;//左移一位相当于乘2
	}
	cout << ans;
	return 0;
}