感觉自己好挫，询问一道动态规划题

leetcode70 爬楼梯问题，我刚开始是用组合和阶乘来算，不出意外的内存溢出了。看了题解要用动态规划，说思路是：

1. 一个人到达第 i 层楼底包括两种方法：
   
2. 
   
3. 选择从第 i-1 层再爬1步到
   
4. 选择从第 i-2 层再爬2步到
   

复制代码

我就不明白了，为什么从第i-2层只爬2步到？剩下的2步就不能分成一步一步的爬嘛？

感觉自己好挫，动态规划都理解不了，涉及递归的理解起来都有点困难。

剩下的2步就不能分成一步一步的爬嘛？

当然可以，但是这样的话，会先从i-2级爬到i-1级。然后再爬一步到达i级。仔细看后半部分“从i-1级爬1步到i”这种方式已经被“第一种方法”涵盖了，不应该在“第二种方法”中再将这种方式讨论一遍。

总之，用动态规划解题时，一般是把问题分割成数个子问题。你要保证这些子问题的分割方式1.考虑了所有的情况，同时2.没有把某些情况计入多次。具体到这个问题：
---
因为上到i层之前那一层一定是"i-1"或"i-2"层，所以我们考虑的“从i-1层出发”和“从i-2层出发”两种方法一定涵盖了所有的爬法；
因为最后一步爬1层和最后一步爬2层这两种方式明显会造成两类不重叠的爬法，所以两种方法之间没有重叠情况。
---
所以你就可以相信这个递推关系一定是正确的了。如果你还是觉得不好理解，可以考虑一个数字较小的情况，比如i=4时，将所有情况列举出来去验证这个递推式。

为什么从第i-2层只爬2步到？剩下的2步就不能分成一步一步的爬嘛？ 当然可以分成一步一步。 不过你先爬出的一步已经算在  爬到 i-1 层的方法数里了， 再算就重复了。

楼上已经解释了dp问题归根结底就是大问题可以拆解成小问题，用递归解中间过程中会有重复的情况，可以用array暂存结果。
针对你的问题，思考一下
假设i=4
那么所有情况就是
1 1 1(3) 1，1 2(2) 1，2 1(3) 1，1 1(2) 2 括号内为当前位置
你要到达第4层的方法数 就是 到达第3层加上最后跨的这一步，以及到达第2层加上最后跨两步.
表达式即为dp[4] = dp[3] + dp[2];
那么想想i=3的情况呢？
1 1(2) 1, 2(2) 1,  1(1) 2
一样，要到达第3层的方法数就是 到达第2层加上最后跨一步，以及到达第1层就上最后跨两步。
dp[3] = dp[2] + dp[1];
以此类推，动态划归最重点的就是想清楚子问题，然后就是弄好数组的初始值，比如这题dp[0], dp[1] 要设为1

My experience the DP problem is easier to start with the recursion answer.
Then you can try to unfold the loop.
For example, your question I think is leetcode 70 which can be solved by following.
1. recursion from climbstair(n-1) + climbstair(n-2)
2. base case is climbstair(0..2)
3. unfold the loop found that
climbstair(3) =  climbstair(2) + climbstair(1)
climbstair(4) =  climbstair(3) + climbstair(2)
...
climbstair(n) =  climbstair(n-1) + climbstair(n-2)

my humble opinion for your reference.