- 一、问题描述
- 二、思路分析
- 三、代码实现
- 四、补充
普通版：
上楼梯的同学，每次可以⾛⼀个台阶，也可以⾛两个台阶，现在有N个台阶，请问有多少种不同的方法？（先爬1阶再爬2阶和先爬2阶再爬1阶是不同的方法）
变态版：
有一个n级台阶的楼梯，小明一次可以向上跳一步，两步，甚至是n步，请问小明跳到n级台阶有多少种方法？
二、思路分析普通版本
变态版本
三、代码实现//跳台阶 #include四、补充//普通版 int fun1(int n) { //输入默认为正整数 if (n == 1) return 1; else if (n == 2) return 2; else return fun1(n - 1) + fun1(n - 2); } //变态版 int fun2(int n) { if (n > 1) return 2 * fun2(n - 1); return 1; } int main() { int n; scanf("%d", &n); int ret1 = fun1(n); int ret2 = fun2(n); printf("%dn", ret1); printf("%dn", ret2); return 0; }
【三特点四要素两本质】
1.什么是动态规划？
动态规划的本质，是对问题状态的定义和 状态转移方程的定义。
状态定义的要求：定义的状态一定要形成递推关系。
2.动态规划有什么特点？
- 把原来的问题分解成为了几个相似的子问题。
- 所有的子问题都只需要解决一次。
- 储存子问题的解。
3.怎样解决动态规划的问题？
一般从以下四个角度考虑
- 状态定义
- 状态间的转移方程定义
- 状态的初始化
- 返回结果
4.动态规划与递归有什么联系与区别？
递归和动态编程(Dynamic Programming, DP)是算法类问题中的难点所在。算法的核心在于找到状态转移方程，即如何通过子问题解决原问题。
相似
递归和动态编程能解决的问题都有一个特性：原问题(problem)可以分解成若干个子问题(sub-problem)，只有先解决了子问题才能进一步解决原问题。子问题的解决方式形式上与原问题一致。
区别
DP和递归有什么不同？最大的区别在于，DP存储子问题的结果，当子问题已经被计算过，直接返回结果。因此，当需要重复计算子问题时，DP的时间效率高很多，但需要额外的空间。
递归的时间成本随递归深度n(单条路径中递归调用的次数)成指数增长；空间复杂度为O(n)。
动态编程的核心在于，如果在一个问题的解决方案中，子问题被重复计算，那么就可以利用记录中间结果，达到用空间换取时间的目的。
参考：DP与递归的异同(https://blog.csdn.net/QilanAllen/article/details/100805998)
