动态规划五部曲

1.确定dp数组以及下标的含义

2.确定递推公式

3.dp数组如何初始化

4.确定遍历顺序

5.举例推导dp数组

509.斐波那契数

  • 动规解法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    /**
     * @param {number} n
     * @return {number}
     */
    /**
    * 动态规划五部曲
    1.确定dp数组以及下标的含义
    dp[i]的定义为：第i个数的斐波那契数值是dp[i]
    2.确定递推公式
    题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
    3.dp数组如何初始化
    dp[0] = 0;dp[1] = 1;
    4.确定遍历顺序
    从递归公式dp[i] = dp[i - 1] + dp[i - 2]中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
    5.举例推导dp数组
    0 1 1 2 3 5 8 13 21 34 55
     */
    var fib = function(n) {
        if(n < 2){
            return n
        }
        // 1.确定数组下标 ：dp[i]为斐波那契数列的第i项
        let dp = []
        // 3.初始化
        dp[0] = 0
        dp[1] = 1
        // 4.遍历顺序
        for(let i = 2; i <= n; i ++){
            // 2.递推公n
            dp[i] = dp[i - 1] + dp[i - 2] 
        }
        return dp[n]
    };

  • 当然，这题用递归超简单

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    /**
     * @param {number} n
     * @return {number}
     */

    var fib = function(n) {
        if(n < 2){
            return n
        }

        return fib(n - 1)+ fib(n - 2)
    };

70.爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {number} n
 * @return {number}
 */
/**
1.确定dp数组以及下标的含义
dp[n]的定义为：n阶楼梯爬上去的方法数量是dp[n]
2.确定递推公式 :
第n-2层再跨2层就到n层  第n - 1层再跨1层到n层
那么现在以及知道了去n-2层和n-1层的方法数，就从这两层开始跳就行了
n-1层 -> n层  跳1步
n-2层 -> n层  一次跳两步 （一步一步的跳会到n - 1层 就重复了）
状态转移方程 dp[n] = dp[n - 2] + 2;
3.dp数组如何初始化
dp[0] = 0 ;dp[1] = 1;dp[2] = 2;
4.确定遍历顺序
从递归公式dp[n] = dp[n - 2] + 2;中可以看出，dp[n]是依赖dp[n - 2]，那么遍历的顺序一定是从前到后遍历的
5.举例推导dp数组
0 1 2 
 */
var climbStairs = function(n) {
    if( n < 3){
        return n
    }
    let dp = []
    dp[1] = 1
    dp[2] = 2
    for(let i = 3; i <= n; i ++){
        dp[i] = dp[i - 1] + dp[i -2]
    }
    return dp[n]
};

746.使用最小花费爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * @param {number[]} cost
 * @return {number}
 */
 /**
1.确定dp数组以及下标的含义
dp[n]的定义为：n阶楼梯爬上去的最低花费是dp[n]
2.确定递推公式 :
第n-2层再跨2层就到n层  第n - 1层再跨1层到n层
那么现在假设知道了去n-2层和n-1层的最低花费，就从这两层开始爬就行了
n-1层 -> n层  跳1步
n-2层 -> n层  一次跳两步 （一步一步的跳会到n - 1层 就重复了）
状态转移方程 dp[n] = min(dp[n - 2] + cost[n - 2] ,dp[n - 1] + cost[n - 1]);
3.dp数组如何初始化
dp[0] = 0 ;dp[1] = 1;dp[2] = 2;
4.确定遍历顺序
从递归公式可以看出，遍历的顺序一定是从前到后遍历的
5.举例推导dp数组

 */
var minCostClimbingStairs = function(cost) {
    // 顶层台阶的下标
    let top = cost.length
    // 如果顶层下标为1，只能从0层爬
    if(top === 1){
        return cost[0]
    }
    // 如果顶层下标为2，可以从0层或者1层跳
    if(top === 2){
        return Math.min(cost[0],cost[1])
    }
    let dp = []
    dp[1] = 0
    dp[2] = Math.min(cost[0],cost[1])
    for(let i = 3; i <= top ; i ++){
        // console.log(i,' ',(dp[i - 1] + cost[i - 1]),(dp[i - 2] + cost[i - 2]))
        dp[i] = Math.min((dp[i - 1] + cost[i - 1]),(dp[i - 2] + cost[i - 2]))
    }
    return dp[top]
};

62.不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
 /**
1.确定dp数组以及下标的含义
dp[x][y]的定义为：到达下标为x y的地点的方法
2.确定递推公式 :
知道dp[x-1][y]和dp[x][y-1]后，分别只有一种方法到dp[x][y]
状态转移方程 dp[x][y] = dp[x-1][y] + dp[x][y-1];
3.dp数组如何初始化
dp[0][0] = 0;   dp[0][1] = 1;   dp[1][0] = 1;   dp[1][1] = 2;
4.确定遍历顺序
从递归公式可以看出，遍历的顺序一定是从前到后遍历的
5.举例推导dp数组
0 1 2 
 */
var uniquePaths = function(m, n) {
    if(m  < 2 || n < 2){
        return 1
    }
    // js定义二维数组
   const dp = Array(m).fill().map(item => Array(n))
for (let i = 0; i < m; ++i) {
        dp[i][0] = 1
    }

    for (let i = 0; i < n; ++i) {
        dp[0][i] = 1
    }
    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
};

63.不同路径Ⅱ

动态规划 初始化比较麻烦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
  /**
1.确定dp数组以及下标的含义
dp[x][y]的定义为：到达下标为x y的地点的方法
2.确定递推公式 :
如果dp[x-1][y]和dp[x][y-1]没有障碍物
知道dp[x-1][y]和dp[x][y-1]后，分别只有一种方法到dp[x][y]
dp[x-1][y]或dp[x][y-1]其中有一个有障碍物
那么就只有另外一个点能走
状态转移方程 dp[x][y] = dp[x-1][y]（障碍物？） + dp[x][y-1]（障碍物？）;
3.dp数组如何初始化
第一行和第一列  在遇到障碍物前  都是1 遇到障碍物后都00是0
4.确定遍历顺序
从递归公式可以看出，遍历的顺序一定是从前到后遍历的
5.举例推导dp数组
0 1 2 
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    // 网格高度（y轴）
    let m = obstacleGrid.length
    // 网格长度（x轴） 
    let n = obstacleGrid[0].length
    if(obstacleGrid[0][0] === 1){
        return 0
    }
    if(obstacleGrid[m - 1][n - 1] === 1){
        return 0
    }
    // dp二维数组初始化，装的是方法数量
    let dp = Array(m).fill().map(item => Array(n))
    // 第一列的初始化
    let i = 1
    dp[0][0] = 1
    // 注意这里 先判断大小  再取数组值
    while(i < m && obstacleGrid[i][0] === 0 ){
        dp[i][0] = 1
        i ++
    }
    for( ;i < m;i ++){
        dp[i][0] = 0
    }
    // 第一行的初始化
    let j = 1
    while(j < n && obstacleGrid[0][j] === 0){
        dp[0][j] = 1
        j ++
    }
    for( ;j < n;j ++){
        dp[0][j] = 0       
    }
    // 从左到右，从上往下遍历
    for(let x = 1;x < m; x++){
        for(let y = 1;y < n;y++){
            dp[x][y] = (dp[x - 1][y]+ dp[x][y - 1]) * (!obstacleGrid[x][y])
        }
    }
    return dp[m - 1][n - 1] 
}

343.整数拆分

动态规划 比较难想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param {number} n
 * @return {number}
 */
  /**
1.确定dp数组以及下标的含义
    dp[i] 是i在拆分后的乘积最大值
    dp[i] = j *dp[i  - j](j从1开始遍历)  
    j * (i - j) 是单纯的把整数拆分为两个数相乘，
    而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
2.确定递推公式 :
   dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
   解释 ： 首先比较(i - j) * j, dp[i - j] * j)，看要不要再继续拆
   然后比较dp[i], max((i - j) * j, dp[i - j] * j)，看下一层有没有上一层大
3.dp数组如何初始化
    dp[2] = 1
4.确定遍历顺序

5.举例推导dp数组

 */
var integerBreak = function(n) {
    // dp的含义 ：dp[i] 是i在拆分后的乘积最大值
    let dp = new Array(n + 1).fill(0)
    // 初始化
    dp[2] = 1

    for(let i = 3; i <= n; i++) {
        for(let j = 1; j <= i / 2; j++) {
            dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j)
        }
    }
    return dp[n]
};

96.不同的二叉搜索树

动态规划 递推公式很困难，需要了解搜索二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * @param {number} n
 * @return {number}
 */
 /**
 二叉搜索树是一个有序树。

    若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    它的左、右子树也分别为二叉排序树
  */
/**
1.确定dp数组以及下标的含义
    dp[n]是由n个节点组成的不同树的最大值
2.确定递推公式 :
    dp[3] == 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
    元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
    元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
    元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
    有2个元素的搜索树数量就是dp[2]。
    有1个元素的搜索树数量就是dp[1]。
    有0个元素的搜索树数量就是dp[0]。
    所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
    dp[i] += dp[j - 1] * dp[i - j]; （遍历j）
3.dp数组如何初始化
    dp[0] = 1 (空结点也是一棵二叉树 说得过去)
4.确定遍历顺序

5.举例推导dp数组
dp[1] = 1  dp[2] = 2  dp[3] = 5
 */
var numTrees = function(n) {
    let dp = new Array(n+1).fill(0);
    dp[0] = 1
    dp[1] = 1
    for(let i = 2;i <= n; i ++ ){
        for(let j = 1;j <= i;j ++){
            dp[i] += dp[j - 1] * dp[i - j] 
        }
    }
    return dp[n]
};