【0014_Week预习】关于爬楼梯问题的思考总结 about algorithm007-class02 HOT 4 OPEN

动态规划问题的主要难点：【状态的定义】和【递推方程】
状态的定义取决于问题有哪几种【选择】，爬楼梯问题中只有两种【选择】：走一步，走两步；这个时候可以从第一个楼梯往后推，可以走到第二层楼梯或者第三层楼梯也就是（F(1)-->F(2)/F(3)），可以适当演化出几层的结果【这里就不展开可以在纸上画一画】；
递推方程：从上面的演化大概能够知道走到第N层的话，就是从第N-1层走上来或者第N-2层走上来；可以演化出递推方程：F(N)=F(N-1)+F(N-2)

from algorithm007-class02.

每次遇到递归或者动态规划的题目都没什么思路，也不知道怎么去找最小重复单元，不知道有没有什么经验可以分享一下的。

from algorithm007-class02.

每次遇到递归或者动态规划的题目都没什么思路，也不知道怎么去找最小重复单元，不知道有没有什么经验可以分享一下的。

找最小重复单元就是找到状态的定义以及状态发生变化后会产生的结果，层层递进的过程，想要掌握需要自己多做题多分析，孰能生巧，动态规划题基本都有模板，自己总结出这些代码模板，动态规划类问题应该就不大

from algorithm007-class02.

每次遇到递归或者动态规划的题目都没什么思路，也不知道怎么去找最小重复单元，不知道有没有什么经验可以分享一下的。

【关于动态规划】
动态规划跟递归可以看作是行进方向不同。递归是从n不断往下调用，n-1,n-2,一直到边界，比如说1.
而动态规划是从底下往上求值，比如，先求1，2，然后根据1，2与3的关系式求得3。依此，由n-2,n-1求得n。
写递归的步骤 = 边界条件 + 缩小规模 + 调用自身
写动态规划的步骤 = 写起始条件 + 分析关系式 + 往上推到指定层次

【爬楼梯中可能陷入的误区】
动态规划的难点其实在于「分析关系式」，如果动态规划的题都直接告知关系式，那基本等于直接告知了解法。
从一般到具体：
具体到爬楼梯这个问题，在于如何得到F(n) = F(n-1) + F(n-2)这关系式。
我曾因为乘法原理陷入一个误区。乘法原理：从A到B有3种走法，从B到C有4种走法，于是从A到B再到C一共有12种走法。我的误区是（错误的想法）：
爬两层台阶有2种方法，爬一层台阶有1种方法。于是F(n) = F(n-1)*1 + F(n-2)*2
我的错误在于，没有意识到，爬两层台阶如果不是直接一步跨2层这种走法，而是走两次1层，则走第1步之后就位于n-1阶位置，然后再走1步到达第n阶，这种走法包含在了从第n-1阶开始，跨1阶走到第n阶的情况里。
简单来说，爬2层台阶有一种方法是以爬1层台阶为后缀，所以只能用一步跨2层台阶的方式才能避免重复，所以F(n-1)和F(n-2)的系数都为1，有关系式子F(n) = F(n-1)*1 + F(n-2)*1
从具体到一般：
虽然不知道是否适用于解决所有DP问题，但是可以有这样的思路：

1. 列出关系项，比如F(n)的数量与F(n-1)和F(n-2)有关
2. 写出可能造成重复系数：爬楼梯问题中，F(n-1)系数为，F(n-2)系数为2,则F(n) = F(n-1)*1 + F(n-2)*2
3. 确定系数，排除重复项，具体方法是检验是否有存在「后缀关系」。比如爬楼梯问题中，爬两级台阶其中一种爬两次1级台阶是以站在第n-1级台阶爬一次1级台阶为后缀的，这种方法确实造成了重复，所以F(n-2)的系数应由2改为1，得到关系式F(n) = F(n-1)*1 + F(n-2)*1
   注：关系式不一定是加法关系，如Leetcode189. 是一个Max()函数的关系

仅供参考，如有错误，还请指出。
---END

from algorithm007-class02.