代码随想录第三十九天

Posted on Edited on In

复习

动态规划五部曲

  1. 确定dp数组含义
  2. 确定递推公式
  3. 确定dp数组初始化
  4. 确定遍历顺序
  5. 推到dp数组，验证

509 斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i < dp.length; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[dp.length - 1];
    }
}

70 爬楼梯

考虑一步到还是两步到的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i < dp.length; i++){
            dp[i] = dp[i - 1] + dp[i - 2]; 
        }

        return dp[dp.length - 1];
    }
}

746 使用最小花费爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        if (cost.length < 2) return 0;
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i < dp.length; i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[dp.length - 1];

    }
}

62 不同路径

思考：

  1. dp[m][n] 是每个格子的步数
  2. 递推公式：每个格子的路径个数是由此格子的左格子加上格子
  3. 初始化：第一行和第一列都是一，即dp[m][0] 和 dp[n][0]都是1
  4. 遍历顺序由上到下，由左到右
  5. 模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++){
            dp[i][0] = 1;
        }

        for (int i = 0; i < n; i++){
            dp[0][i] = 1;
        }

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

        return dp[m - 1][n - 1];
    }
}

63 不同路径II

在上面的题上加入obstacle的条件，如果有obstacle就把数量变成0；

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
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        //如果在起点或终点出现了障碍，直接返回0
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
            return 0;
        }

        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;
        }

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

每日一题 1043 Partition Array for Maximum Sum