1 动态规划( Dynamic Programming)

动态规划的中心思想:在解决当前问题时，可以由之前已经计算所得的结果并结合现在的限制条件递推出结果。由于此前的计算结果已经保留下来，所以极大的缩短了时间复杂度

求解动态规划题目三步骤:

（1） 定义数组;明确数组元素含义；一般求什么就可以定义什么；

比如求第n节台阶需要多少种方式，那么数组元素就是方式的个数

（2）找出初始值：一般规划问题，可能会有会有特殊情况，一般表现在dp[0]、dp[1]；也就是数组中的前两个元素比较特殊；比如第一层和第二层的杨辉三角

（3）归纳出数组之间的关系式；即元素前后的一个关系

这个过程也叫状态表达式；即如何由之前的结果推导出现在的结果；这一步我们再细分一下，有如下三步：

(3.1) 定义内存空间，用来保存每步结果

(3.2) 根据状态转移表达式依次计算每步的结果

(3.3)内存中的数据根据要求作为问题的结果返回。

其实找到这个关系表达式，此类的题目就可以迎刃而解了；中间可能会增加一些限制条件，需要注意一下

2 动态规划应用场景

2.1 计数.比如

有多少种方式走到右下角

有多少种方法选出k个数使得和是Sum

2.2 求最大值最小值.比如

从左上角走到右下角路径的最大数字和

最长上升序列长度

2.3 求存在性.比如

取石子游戏， 先手是否必胜

能不能选出k个数使得和是Sum

3 爬楼梯问题(青蛙跳台阶问题)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

                                            
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
                                            
                                        

                                            
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
                                            
                                        

根据上述步骤尝试；其实挺简单，因为状态表达式很明显就是斐波那契数列，代码如下

                                            
var climbStairs = function(n) {
    let sum=[];
    for(let i=0;i<n;i++){
        if(i===0) sum[0]=1;
        if(i===1) sum[1]=2;
        if(i>1){
            sum[i]=sum[i-1]+sum[i-2];
        }
    }
    return sum[n-1]

};
                                            
                                        

下面这种方法一样的，只不过初始值的表达方式不同

                                            
var climbStairs = function(n) {
    const dp = [0, 1,2]
    for(let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
                                            
                                        

4 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。

                                            
示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:

输入: numRows = 1
输出: [[1]]
                                            
                                        

杨辉三角的初始值以及状态表达式，很容易可以看出来；所以直接根据解题步骤写算法步骤；代码:

                                            
var climbStairs1 = function(numRows) {
    // 第一步 定义数组元素含义，一般求什么就定义什么
    // 因为结果要求第n层的数组，所以定义一个数组表示
    let arr=[];
    if(numRows===0){
        arr=[[]]
        return arr;
    }
    if(numRows===1){
        arr=[[],[1]]
        return arr;
    }
    if(numRows===2){
        arr=[[],[1],[1,1]]
        return arr;
    }
    // 第二步  找出初始值，一般就是dp[0] dp[1]这几个特殊值
    arr=[[],[1],[1,1]]
    // 第三步 归纳出数组元素之间的关系式；叫状态表达式
    for(let i=3;i<numRows+1;i++){
        // 定义一维数组
       arr[i]=[];
       // 初始化第一个和最后一个元素值
       arr[i][0]=arr[i][i-1]=1
        // 遍历赋值中间元素值；归纳得出转移方程
        for(let j=1;j<i-1;j++){
            arr[i][j]=arr[i-1][j-1]+arr[i-1][j];
        }
    }
    return arr.slice(1);
};