题解 | N阶楼梯上楼问题
N阶楼梯上楼问题
https://www.nowcoder.com/practice/c978e3375b404d598f1808e4f89ac551
#include <iostream>
using namespace std;
int main() {
int dp[90] = {0}; //记录中间状态
//店铺[i]表示到第i级台阶的方案数
dp[1] = 1;
dp[2] = 2;
int n;
scanf("%d", &n);
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
printf("%d\n", dp[n]);
return 0;
}
// 64 位输出请用 printf("%lld")
动态规划 空间换时间 文章被收录于专栏
动态规划通常用于求解最优解问题， 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干子问题，先求解子问题， 然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题， 经分解得到的子问题往往不是互相独立的。
