动态规划【Day02】_划分型动态规划

一、坐标型动态规划

115 · 不同的路径 II

题目链接

题目描述：
“不同的路径” 的跟进问题：
有一个机器人位于一个 m×n 网格左上角。

机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。

现在考虑网格中有障碍物，那样将会有多少条不同的路径？

网格中的障碍和空位置分别用 1 和 0 来表示。

样例 1：

• 输入：
  obstacleGrid = [[0]]
• 输出：
  1
  解释：
  只有一个点

样例 2：

• 输入：
  obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
• 输出：
  2
  解释：
  只有 2 种不同的路径

难点：
有障碍，情况分析要添加一种

思路：

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if (m == 0) return 0;
        int n = obstacleGrid[0].length;
        if (n == 0) return 0;

        int[][] f = new int[m][n];
        int i, j;
        for (i = 0; i < m; i++) {
            for (j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    f[i][j] = 0;
                }else {
                    if (i == 0 && j == 0) {
                        f[i][j] = 1;
                    }else {
                        //不能直接套用之前的方法，因为设有障碍，注意两题的差异
//                        if (i == 0 || j == 0) {
//                            f[i][j] = 1;
//                        }else {
//                            f[i][j] = f[i-1][j] + f[i][j-1];
//                        }
                        f[i][j] = 0;
                        if (i-1 >= 0) {
                            f[i][j] += f[i-1][j];
                        }
                        if (j-1 >= 0){
                            f[i][j] += f[i][j-1];
                        }
                    }
                }
            }
        }
        return f[m-1][n-1];
    }
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

尝试使用滚动数组：

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
        return 0;
    }

    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    int[][] f = new int[2][n];
    int i, j;
    int old = 1, now = 0;
    for (i = 0; i < m; i++) {
        // 滚动数组
        old = now;
        now = 1-now;
        for (j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                f[now][j] = 0;
            }else {
                if (i == 0 && j == 0) {
                    f[now][j] = 1;
                }else {
                    f[now][j] = 0;
                    if (i-1 >= 0) {
                        f[now][j] += f[old][j];
                    }
                    if (j-1 >= 0){
                        f[now][j] += f[now][j-1];
                    }
                }
            }
        }
    }
    return f[now][n-1];
}
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

收获：
题目之间有差异，不能套用模板，要具体问题具体分析

397 · 最长上升连续子序列

题目链接

题目描述：
给定一个整数数组（下标从 0 到 n-1， n 表示整个数组的规模），请找出该数组中的最长上升连续子序列。（最长上升连续子序列可以定义为从右到左或从左到右的序列。

样例 1：

• 输入：[5, 4, 2, 1, 3]
• 输出：4
  解释：
  给定 [5, 4, 2, 1, 3]，其最长上升连续子序列（LICS）为 [5, 4, 2, 1]，返回 4。

样例 2：

• 输入：[1, 5, 2, 3, 4]
• 输出：3
  解释：
  给定 [1, 5, 2, 3, 4]，其最长上升连续子序列（LICS）为 [2, 3, 4]，返回 3。

难点：
逐个遍历找连续上升序列

思路：

public class Solution {
    /**
     * @param a: An array of Integer
     * @return: an integer
     */
    int result = 0;
    private void calc(int[] a, int n) {
        int[] f = new int[n];
        int i;
        for (i = 0; i < n; i++) {
            // option 1
            f[i] = 1;
            // option 2
            if (i > 0 && a[i-1] < a[i]) {
                f[i] = f[i-1] + 1;
            }

            if (f[i] > result) {
                result = f[i];
            }
        }

    }

    public int longestIncreasingContinuousSubsequence(int[] a) {
        int n = a.length;
        if (n == 0) return 0;

        calc(a, n);
        // 翻转数组，查看逆序是否存在更大的最大上升连续子序列
        int i, j, t;
        for (i = 0, j = n-1; i < j; i++, j--) {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        calc(a, n);

        return result;
    }
}
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

优化空间复杂度为O(1)

private void calc(int[] a, int n) {
    int[] f = new int[2];
    int i;
    int old, now = 0;
    for (i = 0; i < n; i++) {
        old = now;
        now = 1-now;
        // option 1
        f[now] = 1;
        // option 2
        if (i > 0 && a[i-1] < a[i]) {
            f[now] = f[old] + 1;
        }

        if (f[now] > result) {
            result = f[now];
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

收获：

---

110 · 最小路径和

题目链接

题目描述：
给定一个只含非负整数的m∗n网格，找到一条从左上角到右下角的可以使数字和最小的路径。

样例 1：

• 输入：
  grid = [[1,3,1],[1,5,1],[4,2,1]]
• 输出：
  7
  解释：
  路线为： 1 -> 3 -> 1 -> 1 -> 1

样例 2：

• 输入：
  grid = [[1,3,2]]
• 输出：
  6
  解释：

路线是： 1 -> 3 -> 2

难点：

思路：

public class Solution {
    /**
     * @param grid: a list of lists of integers
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        int[][] f = new int[2][n];
        int old = 1, now = 0;
        int i, j, t1, t2;
        for (i = 0; i < m; i++) {
        	// 滚动数组
            old = now; // old is row i - 1
            now = 1-now; // now is row i
            
            for (j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    f[now][j] = grid[i][j];
                    continue;
                }

                f[now][j] = grid[i][j];
                if (i > 0) {
                    t1 = f[old][j];
                }else {
                    t1 = Integer.MAX_VALUE;
                }

                if (j > 0) {
                    t2 = f[now][j-1]; //f[i][j-1]
                }else {
                    t2 = Integer.MAX_VALUE;
                }

                if (t1 < t2) {
                    f[now][j] += t1;
                }else {
                    f[now][j] += t2;
                }
            }
        }
        return f[now][n-1];
    }
}
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

收获：
滚动数组

---

553 · 炸弹袭击

题目链接

题目描述：
给定一个二维矩阵, 每一个格子可能是一堵墙 W,或者 一个敌人 E 或者空 0 (数字 ‘0’), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固，所以墙不会被摧毁.
样例1

• 输入:
  grid =[
  “0E00”,
  “E0WE”,
  “0E00”
  ]
• 输出: 3
  解释:
  把炸弹放在 (1,1) 能杀3个敌人

样例2

• 输入:
  grid =[ “0E00”, “EEWE”, “0E00”]
• 输出: 2
  解释:
  P把炸弹放在 (0,0) 或 (0,3) 或 (2,0) 或 (2,3) 能杀2个敌人

难点：

思路：

public class Solution {
    /**
     * @param grid: Given a 2D grid, each cell is either 'W', 'E' or '0'
     * @return: an integer, the maximum enemies you can kill using one bomb
     */
    public int maxKilledEnemies(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        int[][] f = new int[m][n];
        int[][] res = new int[m][n];
        int i, j;
        for (i = 0; i < m; i++) {
            for (j = 0; j < n; j++) {
                res[i][j] = 0;
            }
        }
        // up
        for (i = 0; i < m; i++) {
            for (j = 0; j < n; j++) {
                if (grid[i][j] == 'W') {
                    f[i][j] = 0;
                }else {
                    f[i][j] = 0;
                    if (grid[i][j] == 'E') {
                        f[i][j] = 1;
                    }
                    if (i-1 >= 0) {
                        f[i][j] += f[i-1][j];
                    }
                }
                res[i][j] += f[i][j];
            }
        }

        // down
        for (i = m-1; i >= 0; i--) {
            for (j = 0; j < n; j++) {
                if (grid[i][j] == 'W') {
                    f[i][j] = 0;
                }else {
                    f[i][j] = 0;
                    if (grid[i][j] == 'E') {
                        f[i][j] = 1;
                    }
                    if (i+1 < m) {
                        f[i][j] += f[i+1][j];
                    }
                }
                res[i][j] += f[i][j];
            }
        }

        // left
        for (i = 0; i < m; i++) {
            for (j = 0; j < n; j++) {
                if (grid[i][j] == 'W') {
                    f[i][j] = 0;
                }else {
                    f[i][j] = 0;
                    if (grid[i][j] == 'E') {
                        f[i][j] = 1;
                    }
                    if (j-1 >= 0) {
                        f[i][j] += f[i][j-1];
                    }
                }
                res[i][j] += f[i][j];
            }
        }

        // right
        for (i = 0; i < m; i++) {
            for (j = n-1; j >= 0; j--) {
                if (grid[i][j] == 'W') {
                    f[i][j] = 0;
                }else {
                    f[i][j] = 0;
                    if (grid[i][j] == 'E') {
                        f[i][j] = 1;
                    }
                    if (j+1 < n) {
                        f[i][j] += f[i][j+1];
                    }
                }
                res[i][j] += f[i][j];
            }
        }

        int result = 0;
        for (i = 0; i < m; i++) {
            for (j = 0; j < n; j++) {
                if (grid[i][j] == '0') {
                    if (res[i][j] > result) {
                        result = res[i][j];
                    }
                }
                
            }
        }

        return result;
    }
}
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

坐标型动态规划总结

---

二、序列型动态规划

515 · 房屋染色

题目链接

题目描述：
这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小，返回最小的费用。

费用通过一个nx3 的矩阵给出，比如cost[0][0]表示房屋0染红色的费用，cost[1][2]表示房屋1染绿色的费用，依此类推。找到油漆所有房子的最低成本。

样例 1:

• 输入: [[14,2,11],[11,14,5],[14,3,10]]
• 输出: 10
  解释: 第一个屋子染蓝色，第二个染绿色，第三个染蓝色，最小花费：2 + 5 + 3 = 10.

样例 2:

• 输入: [[1,2,3],[1,4,6]]
• 输出: 3

难点：

思路：

注意序列型动态规划和坐标型的差异。

实践的时候枚举不同情况即可。

public class Solution {
    /**
     * @param costs: n x 3 cost matrix
     * @return: An integer, the minimum cost to paint all houses
     */
    public int minCost(int[][] costs) {
        int n = costs.length;
        if (n == 0) return 0;
        //                 n+1 f[0],...,f[n]
        int[][] f = new int[n+1][3];
        int i, j, k, res;
        f[0][0] = f[0][1] = f[0][2] = 0;
        for (i = 1; i <= n; i++) {
            //j is the color of i-1
            for (j = 0; j < 3; j++) {
                f[i][j] = Integer.MAX_VALUE;
                //k is the color of i-2
                for (k = 0; k < 3; k++) {
                    if (j == k) continue;
                    if (f[i-1][k] + costs[i-1][j] < f[i][j]) {
                        f[i][j] = f[i-1][k] + costs[i-1][j];
                    }
                }
            }
        }
        res = Math.min(Math.min(f[n][0], f[n][1]), f[n][2]);
        return res;
    }
}
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

收获：
注意一下表述：这里前i个指的是，0…i-1，这i个

664 · 数 1

题目链接

题目描述：
给出一个 非负 整数 num，对所有满足 0 ≤ i ≤ num 条件的数字 i 均需要计算其二进制表示中数字 1 的个数并以数组的形式返回。

样例1

• 输入： 5
• 输出： [0,1,1,2,1,2]
  解释：
  0~5的二进制表示分别是：
  000
  001
  010
  011
  100
  101
  每个数字中1的个数为： 0,1,1,2,1,2

样例2

• 输入： 3
• 输出： [0,1,1,2]

public class Solution {
    /**
     * @param num: a non negative integer number
     * @return: an array represent the number of 1's in their binary
     */
    public int[] countBits(int num) {
        int[] f = new int[num+1];
        f[0] = 0;
        for (int i = 1; i <= num; i++) {
            f[i] = f[i >> 1] + (i % 2);
        }
        return f;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

三、划分型动态规划

512 · 解码方法

题目链接

题目描述：
有一个消息包含A-Z通过以下规则编码
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
现在给你一个加密过后的消息，问有几种解码的方式

样例 1:
输入: “12”
输出: 2
解释: 它可以被解码为 AB (1 2) 或 L (12).

样例 2:
输入: “10”
输出: 1

难点：

思路：

时间复杂度：O()
空间复杂度：O()

public class Solution {
    /**
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
    public int numDecodings(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        if (n == 0) return 0;
        //                n + 1
        int[] f = new int[n+1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i] = 0;
            //倒数第一个数
            int t = chars[i-1] - '0';
            if (t >= 1 && t <= 9) {
                f[i] += f[i-1];
            }
			// 必须要满足长度比1大
            if (i >= 2) {
            	// 倒数第二个数
                t = chars[i-1] - '0' + (chars[i-2] - '0')*10;
                if (t >=10 && t <= 26) {
                    f[i] += f[i-2];
                }
            }
        }
        return f[n];
    }
}
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

收获：
对前i个的理解加深

在Java中，对于字符串的遍历，建议采用：
String.toCharArray()的方法
字符串—>字符数组
使用下标遍历更方便
不然每次都要调用String.charAt(i)这个方法

---

题目链接

题目描述：

难点：

思路：

收获：