动态规划问题

解题思路

1. 先分析dp各下标及其对应值代表的含义
2. 写出状态转移方程
3. 初始化dp数组
4. 确认遍历顺序
5. 打印dp数组来debug

示例

跳台阶

问题

给定一个共有 𝑛 阶的楼梯，你每步可以上 1 阶或者 2 阶，请问有多少种方案可以爬到楼顶？

解题思路

1. 分析题目，求解到达最后一个台阶的方案，简化为到达第i哥台阶的方案数；设置dp数组，设置为一维数组dpn + 1，dp[i]代表到达第i个台阶的方案数

2. 第i个台阶只能由第i - 1或i - 2各台阶跳上去，因此dp[i] = dp[i - 1] + dp[i - 2];

3. 初始化dp数组，第一个台阶只有一种方案，第二个台阶有两个，因此dp[1] = 1;dp[2] = 2;

4. 确认遍历顺序，dp前两个已经确定，直接从dp[3] 开始往后循环遍历(从前往后跳，后面台阶方案数需要使用到前面台阶方案数的数据)

5. 打印dp数组来debug