Dynamic Programming

自底向上的动态规划

509. 斐波那契数

方法一：暴搜

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int fib(int n) {
        return dfs(n);
    }

    private int dfs(int index) {
        if (index == 0 || index == 1)
            return index;
        return dfs(index - 1) + dfs(index - 2);
    }
}

方法二：记忆化搜索

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

    int[] dp;

    private int dfs(int index) {
        if (index == 0 || index == 1)
            return index;
        if (dp[index] != 0)
            return dp[index];
        return dp[index] = dfs(index - 1) + dfs(index - 2);
    }
}

方法三：DP

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1)
            return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; ++i)
            dp[i] = dp[i - 2] + dp[i - 1];
        return dp[n];
    }
}

方法四：DP + 滚动数组

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1)
            return n;
        int[] dp = new int[3];
        dp[1] = 1;
        for (int i = 2; i <= n; ++i)
            dp[i % 3] = dp[(i - 2) % 3] + dp[(i - 1) % 3];
        return dp[n % 3];
    }
}

198. 打家劫舍

方法一：暴搜

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int rob(int[] nums) {
        return dfs(nums, nums.length - 1);
    }
    private int dfs(int[] nums, int index) {
        if (index == 0 || index < 0)
            return index == 0 ? nums[0] : 0;
        return Math.max(dfs(nums, index - 2) + nums[index], dfs(nums, index - 1));
    }
}

方法二：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int[] dp;
    public int rob(int[] nums) {
        dp = new int[nums.length];
        Arrays.fill(dp, -1);
        return dfs(nums, nums.length - 1);
    }
    private int dfs(int[] nums, int index) {
        if (index == 0 || index < 0)
            return index == 0 ? nums[0] : 0;
        if (dp[index] != -1)
            return dp[index];
        return dp[index] = Math.max(dfs(nums, index - 2) + nums[index], dfs(nums, index - 1));
    }
}

方法三：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int rob(int[] nums) {
        // dp[i]：经过第i个房间能获得的最大价值
        if (nums.length == 1)
            return nums[0];
        if (nums.length == 2)
            return Math.max(nums[0], nums[1]);
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; ++i) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}

方法四：DP + 滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int rob(int[] nums) {
        // dp[i]：经过第i个房间能获得的最大价值
        if (nums.length == 1)
            return nums[0];
        if (nums.length == 2)
            return Math.max(nums[0], nums[1]);
        int[] dp = new int[3];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; ++i) {
            dp[i % 3] = Math.max(dp[(i - 1) % 3], dp[(i - 2) % 3] + nums[i]);
        }
        return dp[(nums.length - 1) % 3];
    }
}

64. 最小路径和

方法一：回溯

回溯一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minPathSum(int[][] grid) {
        dfs(grid, 0, 0, 0);
        return res;
    }
    int res = 8000000;
    private void dfs(int[][] grid, int i, int j, int sum) {
        if (i == grid.length || j == grid[0].length)
            return;
        sum += grid[i][j];
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            res = Math.min(res, sum);
            return;
        }
        dfs(grid, i + 1, j, sum);
        dfs(grid, i, j + 1, sum);
    }
}

回溯二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minPathSum(int[][] grid) {
        dfs(grid, 0, 0, 0);
        return res;
    }
    int res = 8000000;
    private int dfs(int[][] grid, int i, int j, int sum) {
        if (i == grid.length || j == grid[0].length)
            return 0;
        sum += grid[i][j];
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            res = Math.min(res, sum);
            return sum;
        }
        return dfs(grid, i + 1, j, sum) + dfs(grid, i, j + 1, sum);
    }
}

方法二：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minPathSum(int[][] grid) {
        dp = new int[grid.length][grid[0].length];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(grid, 0, 0);
    }
    int[][] dp;
    private int dfs(int[][] grid, int i, int j) {
        if (i == grid.length || j == grid[0].length)
            return 8000000;
        if (dp[i][j] != -1)
            return dp[i][j];
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            return grid[i][j];
        }
        return dp[i][j] = grid[i][j] + Math.min(dfs(grid, i + 1, j), dfs(grid, i, j + 1));
    }
}

方法三：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minPathSum(int[][] grid) {
        // dp[i][j]:走到grid[i][j]的最小路径
        // 状态转移：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        // 初始化：第0行和第0列
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < grid.length; ++i)
            dp[i][0] += dp[i - 1][0] + grid[i][0];
        for (int j = 1; j < grid[0].length; ++j)
            dp[0][j] += dp[0][j - 1] + grid[0][j];
        for (int i = 1; i < grid.length; ++i) {
            for (int j = 1; j < grid[0].length; ++j) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[grid.length - 1][grid[0].length - 1];
    }
}

62. 不同路径

方法一：回溯

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int uniquePaths(int m, int n) {
        return dfs(m, n, 1, 1);
    }
    private int dfs(int m, int n, int i, int j) {
        if (i == m + 1 || j == n + 1)
            return 0;
        if (i == m && j == n)
            return 1;
        return dfs(m, n, i + 1, j) + dfs(m, n, i, j + 1);
    }
}

方法二：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int uniquePaths(int m, int n) {
        dp = new int[m + 1][n + 1];
        return dfs(m, n, 1, 1);
    }
    int[][] dp;
    private int dfs(int m, int n, int i, int j) {
        if (i == m + 1 || j == n + 1)
            return 0;
        if (i == m && j == n)
            return 1;
        if (dp[i][j] != 0)
            return dp[i][j];
        return dp[i][j] = dfs(m, n, i + 1, j) + dfs(m, n, i, j + 1);
    }
}

方法三：组合数学

res = res * i / j不能写成*=，因为可能i / j不为整数

1
2
3
4
5
6
7
8
class Solution {
    public int uniquePaths(int m, int n) {
        long res = 1;
        for (int i = n, j = 1; j < m; ++i, ++j)
            res = res * i / j;
        return (int) res;
    }
}

方法四：DP

第0行第0列赋值1，反正后面都会被覆盖，干脆全赋值1

1
2
for (int[] arr : dp)
    Arrays.fill(arr, 1);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1)
            return 1;
        int[][] dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, 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];
    }
}

方法五：DP + 滚动数组(两行)

边界都是1，所以可以滚动，不同路径那题不行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1)
            return 1;
        int[][] dp = new int[2][n];
        for (int[] arr : dp)
            Arrays.fill(arr, 1);
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i % 2][j] = dp[(i - 1) % 2][j] + dp[i % 2][j - 1];
            }
        }
        return dp[(m - 1) % 2][n - 1];
    }
}

方法五：DP + 滚动数组(一行)

这里把数组全部初始化为1，是为了模拟第0行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1)
            return 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[j] += + dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

63. 不同路径 II

方法一：回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        return dfs(obstacleGrid, m, n, 0, 0);
    }
    private int dfs(int[][] obstacleGrid, int m, int n, int i, int j) {
        if (i == m || j == n || obstacleGrid[i][j] == 1)
            return 0;
        if (i == m - 1 && j == n - 1)
            return 1;
        return dfs(obstacleGrid, m, n, i + 1, j) + dfs(obstacleGrid, m, n, i, j + 1);            
    }
}

方法二：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(obstacleGrid, m, n, 0, 0);
    }
    int[][] dp;
    private int dfs(int[][] obstacleGrid, int m, int n, int i, int j) {
        if (i == m || j == n || obstacleGrid[i][j] == 1)
            return 0;
        if (i == m - 1 && j == n - 1)
            return 1;
        if (dp[i][j] != -1)
            return dp[i][j];
        return dp[i][j] = dfs(obstacleGrid, m, n, i + 1, j) + dfs(obstacleGrid, m, n, i, j + 1);            
    }
}

方法三：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            if (obstacleGrid[i][0] == 1)
                break;
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            if (obstacleGrid[0][j] == 1)
                break;
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (obstacleGrid[i][j] == 1)
                    continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

方法五：DP + 滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                    continue;
                }
                if (j >= 1 && obstacleGrid[i][j - 1] == 0)
                    dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

980. 不同路径 III

方法一：回溯 先放错误版本，debug1个多小时

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
class Solution {
    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        int[] oriIndex = null;
        int left = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0)
                    ++left;
                else if (grid[i][j] == 1)
                    oriIndex = new int[]{i, j};
            }
        }
        return dfs(oriIndex[0], oriIndex[1], left + 1);
    }

    private int dfs(int i, int j, int left) {
        if (grid[i][j] == 2)
            return left == 0 ? 1 : 0;
        int res = 0;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] != -1) {
               int temp1 = grid[row][col];
               grid[row][col] = -1;
                res += dfs(row, col, left - 1);
               grid[row][col] = temp1;
            }
        }
        return res;
    }


    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }

    int[][] grid, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};;
    int m, n;
}

在错误版本中，是将邻居grid[row][col] = -1;置为以访问状态，那么从i ，j递归到 row, col又可以递归回i,j所以left的次数一定是错的

回溯正确版本

将i,j置为以访问状态

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
class Solution {
    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        int[] oriIndex = null;
        int left = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0)
                    ++left;
                else if (grid[i][j] == 1)
                    oriIndex = new int[]{i, j};
            }
        }
        return dfs(oriIndex[0], oriIndex[1], left + 1);
    }

    private int dfs(int i, int j, int left) {
        if (grid[i][j] == 2)
            return left == 0 ? 1 : 0;
        int res = 0, temp = grid[i][j];
        grid[i][j] = -1;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && (grid[row][col] == 0 || grid[row][col] == 2)) {
                res += dfs(row, col, left - 1);
            }
        }
        grid[i][j] = temp;
        return res;
    }


    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }

    int[][] grid, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};;
    int m, n;
}

118. 杨辉三角

方法一：DP

最后一行的长度是2n - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new LinkedList<>();
        int[][] dp = new int[numRows][numRows * 2 + 1];
        dp[0][dp[0].length / 2] = 1;
        res.add(new LinkedList<>(Arrays.asList(1)));
        for (int i = 1; i < numRows; ++i) {
            List<Integer> list = new LinkedList<>();
            for (int j = 0; j < dp[0].length; ++j) {
                dp[i][j] = (j < dp[0].length - 1 ? dp[i - 1][j + 1] : 0) + (j >= 1 ? dp[i - 1][j - 1] : 0);
                if (dp[i][j] != 0)
                    list.add(dp[i][j]);
            }
            res.add(list);
        }
        return res;
    }
}

方法二：DP

第一列与最后一列是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
class Solution {
    public List<List<Integer>> generate(int numRows) {
        /*
        1
        1 1
        1 2 1
        1 3 3 1
         */
        List<List<Integer>> res = new LinkedList<>();
        List<Integer> row = new LinkedList<>();
        // 第一行
        row.add(1);
        res.add(row);
        for (int i = 2; i <= numRows; ++i) {
            row = new LinkedList<>();
            // 第一列
            row.add(1);
            for (int j = 1; j < i - 1; ++j) 
                row.add(res.get(i - 2).get(j - 1) + res.get(i - 2).get(j));
            // 最后一列
            row.add(1);
            res.add(row); // 在res中的下标为i - 1
        }
        return res;
    }
}

120. 三角形最小路径和

二刷回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        /*
        2
        3 4
        6 5 7
        4 1 8 3
         */
        return dfs(triangle, 0, 0);

    }

    private int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size())
            return 0;
        return triangle.get(i).get(j) + Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 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
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        /*
        2
        3 4
        6 5 7
        4 1 8 3
         */
        dp = new int[triangle.size()][triangle.size()];
        for (int[] arr : dp)
            Arrays.fill(arr, 10001);
        return dfs(triangle, 0, 0);
    }

    int[][] dp;

    private int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size())
            return 0;
        if (dp[i][j] != 10001)
            return dp[i][j];
        return dp[i][j] = triangle.get(i).get(j) + Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1));
    }
}

二刷DP

dp数组多创建一列，把dp数组初始化为10001，处理第一列没有左上方元素与最后一列没有正上方元素的特殊情况

1
int[][] dp = new int[triangle.size()][triangle.size() + 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
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        /*
        2
        3 4
        6 5 7
        4 1 8 3
         */
        if (triangle.size() == 1)
            return triangle.get(0).get(0);
        // dp[i][j]：到达i，j的最短距离
        int[][] dp = new int[triangle.size()][triangle.size() + 1];
        int min = 10001;
        for (int[] arr : dp)
            Arrays.fill(arr, 10001);
        dp[0][1] = triangle.get(0).get(0);
        for (int i = 1; i < triangle.size(); ++i) {
            for (int j = 0; j < triangle.get(i).size(); ++j) {
                dp[i][j + 1] = Math.min(dp[i - 1][j], dp[i - 1][j + 1]) + triangle.get(i).get(j);
                if (i == triangle.size() - 1) 
                    min = Math.min(min, dp[i][j + 1]);
            }
        }
        return min;
    }
}

从最后一行开始遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        /*
        2
        3 4
        6 5 7
        4 1 8 3
         */
        // dp[i][j]：到达i，j的最短距离
        int n = triangle.size();
        int[][] dp = new int[n + 1][n + 1];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}

方法一：回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] list = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i + 1; ++j) {
                list[i][j] = triangle.get(i).get(j);
            }
        }
        return dfs(list, n, 0, 0);
    }

    private int dfs(int[][] list, int n, int i, int j) {
        if (j > i)
            return 0;
        if (i == n - 1)
            return list[i][j];
        return Math.min(dfs(list, n, i + 1, j), dfs(list, n, i + 1, j + 1)) + list[i][j];
    }
}

方法二：记忆化搜索一

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
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] list = new int[n][n];
        dp = new int[n][n];
        for (int[] arr : dp)
            Arrays.fill(arr, Integer.MAX_VALUE);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i + 1; ++j) {
                list[i][j] = triangle.get(i).get(j);
            }
        }
        return dfs(list, n, 0, 0);
    }
    int[][] dp;
    private int dfs(int[][] list, int n, int i, int j) {
        if (j > i)
            return 0;
        if (i == n - 1)
            return list[i][j];
        if (dp[i][j] != Integer.MAX_VALUE)
            return dp[i][j];
        return dp[i][j] = Math.min(dfs(list, n, i + 1, j), dfs(list, n, i + 1, j + 1)) + list[i][j];
    }
}

image-20230527210340694

优化记忆化搜索

只改动了base case

i == n-1就直接返回，会使最后一次dp信息漏掉，如果最后一行很长，那么会多进入dfs很多次

注意最后一行

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
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] list = new int[n][n];
        dp = new int[n][n];
        for (int[] arr : dp)
            Arrays.fill(arr, Integer.MAX_VALUE);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i + 1; ++j) {
                list[i][j] = triangle.get(i).get(j);
            }
        }
        return dfs(list, n, 0, 0);
    }
    int[][] dp;
    private int dfs(int[][] list, int n, int i, int j) {
        if (j > i)
            return 0;
        if (i == n)
            return 0;
        if (dp[i][j] != Integer.MAX_VALUE)
            return dp[i][j];
        return dp[i][j] = Math.min(dfs(list, n, i + 1, j), dfs(list, n, i + 1, j + 1)) + list[i][j];
    }
}

方法三：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        for (int[] arr : dp)
            Arrays.fill(arr, Integer.MAX_VALUE);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i + 1; ++j) {
                int pre = 0;
                if (i >= 1) {
                    pre = dp[i - 1][j];
                    if (j >= 1)
                        pre = Math.min(pre, dp[i - 1][j - 1]);
                }
                dp[i][j] = triangle.get(i).get(j) + pre;
                if (i == n - 1)
                    res = Math.min(res, dp[i][j]);
            }
        }
        return res;
    }
}

方法四：DP + 滚动数组

和01背包类似，第二次for循环要倒序遍历；如果正序遍历那么pre = dp[j]拿到的是第i行的数据，我们需要的是第i-1行的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        Arrays.fill(dp, 1000000);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            for (int j = i; j >= 0; --j) {
                int pre = 0;
                if (i >= 1) {
                    pre = dp[j];
                    if (j >= 1)
                        pre = Math.min(pre, dp[j - 1]);
                }
                dp[j] = triangle.get(i).get(j) + pre;
                if (i == n - 1)
                    res = Math.min(res, dp[j]);
            }
        }
        return res;
    }
}

279. 完全平方数

完全背包问题

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int numSquares(int n) {
        int m = (int) Math.sqrt(n);
        int[] nums = new int[m];
        for (int i = 0; i < m; ++i) {
            nums[i] = (i + 1) * (i + 1);
        }
        // dp[j]:容量为j的背包最少需要多少个数字填满
        // dp[0] = 0
        int[] dp = new int[n + 1];
        for (int i = 1; i < dp.length; ++i)
            dp[i] = 10001;
        for (int i = 0; i < nums.length; ++i) {
            for (int j = nums[i]; j <= n; ++j) {
                dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1);
            }
        }
        return dp[n];
    }
}

377. 组合总和 Ⅳ

思路：

  1. 排列问题
  2. 爬楼梯问题

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int combinationSum4(int[] nums, int target) {
        // dp[i]:组成i的排列种数
        // dp[i] += dp[i - nums[j]]
        // dp[0] = 1，后面状态根据1往上加
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (int j = 0; j < nums.length; ++j) {
                if (i >= nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}

如果要求返回所有排列数，如下

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
package 背包;

import java.util.*;

public class Solution {
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum4(int[] nums, int target) {
        backtracking(nums, target, 0);
        return res;
    }

    private void backtracking(int[] nums, int target, int index) {
        if (target == 0) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = index; i < nums.length; ++i) {
            if (target < nums[i])
                break;
            path.offerLast(nums[i]);
            backtracking(nums, target - nums[i], index);
            path.pollLast();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.combinationSum4(new int[]{1, 2, 3}, 4));
    }
}

300. 最长递增子序列

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLIS(int[] nums) {
        // dp[j]: 以下标j结尾的最长递增子序列的长度
        int res = 1;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                if (nums[j] > nums[i]) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
                res = Math.max(res, dp[j]);
            }
        }
        return res;
    }
}

二刷DP：从前往后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 1)
            return 1;
        // dp[i]：下标为i前的子数组的最长递增子序列的长度
        int[] dp = new int[nums.length];    
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < nums.length; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    res = Math.max(res, dp[i]);
                }
            }
        }
        return res;
    }
}

方法二：贪心 + 二分

674. 最长连续递增序列

方法一：暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        // dp[j]: 以下标j为结尾的子数组的长度
        int res = 1;
        for (int i = 0; i < nums.length; ++i) {
            int length = 1;
            for (int j = i + 1; j < nums.length; ++j) {
                if (nums[j] > nums[j - 1]) {
                    ++length;
                res = Math.max(res, length);
                }
                else {
                    length = 1;
                }
            }
        }
        return res;
    }
}

方法二：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        // dp[j]: 以下标j为结尾的最长连续递增序列的长度
        // dp[j] = dp[j - 1] + 1
        // dp[:] = 1
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }
}

方法三：DP + 滚动数组

如果nums[i] <= nums[i-1]，记得dp[i % 2] = 1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        // dp[j]: 以下标j为结尾的最长连续递增序列的长度
        // dp[j] = dp[j - 1] + 1
        // dp[:] = 1
        int[] dp = new int[2];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > nums[i - 1]) {
                dp[i % 2] = dp[(i - 1) % 2] + 1;
                res = Math.max(res, dp[i % 2]);
            }
            else {
                dp[i % 2] = 1;
            }
        }
        return res;
    }
}

718. 最长重复子数组

动动脑子吧你

方法一：暴力

  1. 时间复杂度：\(O(m^2n)\)
  2. 空间复杂度：\(O(1)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int res = 0;
        for (int i = 0; i < nums1.length; ++i) {
            for (int j = 0; j < nums2.length; ++j) {
                int count1 = i, count2 = j;
                int counter = 0;
                while (count1 < nums1.length && count2 < nums2.length && nums1[count1] == nums2[count2]) {
                    ++counter;
                    ++count1;
                    ++count2;
                }
                res = Math.max(res, counter);
            }
        }
        return res;
    }
}

方法二：DP

  1. dp[i][j]:以nums1[i - 1]结尾与以nums2[j - 1]结尾时的最长重复子数组
  2. 状态转移公式：当nums1[i - 1] == nums2[j - 1]时，dp[i][j] = dp[i - 1][j - 1] + 1
  3. 初始化：m为nums1的长度，n为nums2的长度，初始化(m + 1) * (n + 1)的二维数组，第一行第一列初始化为0，因为任一数组为空，就不会有重复子数组
  4. 注意事项：输出结果是dp数组中的最大值，因为最长的重复子数组不一定是在两数组的结尾处，可以在循环内比较
  5. 时间复杂度：\(O(mn)\)
  6. 空间复杂度：\(O(mn)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        int result = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    result = Math.max(result, dp[i][j]);
                }
            }
        }
        return result;
    }
}

滚动数组缩减空间复杂度

  1. dp数组为第二个数组的长度加一

  2. 不相等时要把dp[j]赋0，不然之后会出错

  3. 此时遍历第二个数组的时候，就要从后向前遍历，这样避免重复覆盖。

    比如nums1 = [1, 2, 3, 1],nums2 = [1,6,8,1,3,1,2,3]

    i = 1时候，dp数组为[1,0,0,1,0,1,0,0]

    i = 2时候，dp数组为[0,0,0,0,0,0,1,0]

    i = 3时候，dp数组为[0,0,0,0,1,0,0,2]

    image-20230418180633319

    i=3时，如果第二层for循环j从前往后遍历，那么dp倒数第二个位置会因为3!=2，被赋0，进而导致dp最后一个位置是1而不是2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[] dp = new int[nums2.length + 1];
        int res = 0;
        for (int i = 1; i <= nums1.length; ++i) {
            for (int j = nums2.length; j > 0; --j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                }
                else {
                    dp[j] = 0;
                }
                res = Math.max(res, dp[j]);
            }
        }
        return res;
    }
}

1143. 最长公共子序列

方法三：滚动数组(一行)

用pre记录左上角的值

计算当前值之前，先用temp保存dp[j + 1]，计算完dp[j + 1]，将temp赋值给pre

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 longestCommonSubsequence(String s, String t) {
        int m = s.length(), n = t.length();
        // dp[i][j]: s[:i]与t[:j]的最长公共子序列长度
        // if s[i] == t[j]: dp[i][j] = 1 + dp[i - 1][j - 1]
        // else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) 
        int[] dp = new int[n + 1];
        for (int i = 0; i < m; ++i) {
            int pre = 0;
            for (int j = 0; j < n; ++j) {
                int temp = dp[j + 1];
                if (s.charAt(i) == t.charAt(j))
                    dp[j + 1] = pre + 1;
                else
                    dp[j + 1] = Math.max(dp[j], dp[j + 1]);
                pre = temp;
            }
        }
        return dp[n];
    }
}

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // dp[i][j]: text1以i为结尾，text2以j为结尾的最长公共子序列长度
        // text[i - 1] == text[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1
        // text[i - 1] != text[j - 1]:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for (int i = 1; i <= text1.length(); ++i) {
            for (int j = 1; j <= text2.length(); ++j) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

方法二：DP + 滚动数组(两行)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // dp[i][j]: text1以i为结尾，text2以j为结尾的最长公共子序列长度
        // text[i - 1] == text[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1
        // text[i - 1] != text[j - 1]:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        int[][] dp = new int[2][text2.length() + 1];
        for (int i = 1; i <= text1.length(); ++i) {
            for (int j = 1; j <= text2.length(); ++j) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
                }
                else {
                    dp[i % 2][j] = Math.max(dp[i % 2][j - 1], dp[(i - 1) % 2][j]);
                }
            }
        }
        return dp[text1.length() % 2][text2.length()];
    }
}

583. 两个字符串的删除操作

方法一：最长公共子序列

  1. 代码和最长公共子序列一模一样，只是返回值不同
  2. 找出最长公共子序列长度为x，然后用word1的长度 + word2的长度 - x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minDistance(String text1, String text2) {
        // dp[i][j]: text1以i为结尾，text2以j为结尾的最长公共子序列长度
        // text[i - 1] == text[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1
        // text[i - 1] != text[j - 1]:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        int[][] dp = new int[2][text2.length() + 1];
        for (int i = 1; i <= text1.length(); ++i) {
            for (int j = 1; j <= text2.length(); ++j) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
                }
                else {
                    dp[i % 2][j] = Math.max(dp[i % 2][j - 1], dp[(i - 1) % 2][j]);
                }
            }
        }
        // return dp[text1.length() % 2][text2.length()];
        return text1.length() + text2.length() - dp[text1.length() % 2][text2.length()] * 2;
    }
}

方法二：DP

  1. dp[i][j]：使得以i为结尾的子串sub1与以j为结尾的子串sub2相同所需的最少删除次数

  2. m为word1的长度，n为word2的长度，创建大小为(m + 1) * (n + 1)大小的dp数组，首先需要初始化第0行与第0列，初始化第0行表示使为空字符串的sub1与长度为j的子串sub2相同所需的最少删除次数，举例word1 = “sea”，word2 = “eeat”，空字符串与空字符串：0，空字符串与“e”：1，空字符串与“ee”：2，空字符串与“eea”：3，空字符串与“eeat”：4。

    初始化第0列类似。以下为初始化dp数组

    0 1 2 3 4
    1 0 0 0 0
    2 0 0 0 0
    3 0 0 0 0

  3. 状态转移方程：

    1. 如果两个字符i、j相同，那么所需删除的次数和没加入这两个字符所需要的次数一致

      1
      2
      if (word1.charAt(i - 1)  == word2.charAt(j - 1))
          dp[i][j] = dp[i - 1][j - 1];

    2. 如果两个字符i、j不同，所需删除的次数为如下

      1
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int j = 0; j <= n; ++j)
            dp[0][j] = j;
        for (int i = 0; i <= m; ++i)
            dp[i][0] = i;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1.charAt(i - 1)  == word2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
        return dp[m][n];
    }
}

72. 编辑距离

优质题解

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i)
            dp[i][0] = dp[i - 1][0] + 1;
        for (int j = 1; j <= n; ++j) 
            dp[0][j] = dp[0][j - 1] + 1;
        for (int i = 1; i <= m; ++i) {
            char ch1 = word1.charAt(i - 1);
            for (int j = 1; j <= n; ++j) {
                if (ch1 != word2.charAt(j - 1))
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
                else
                    dp[i][j] = dp[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
}

二刷DP

当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；

当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int j = 1; j <= n; ++j)
            dp[0][j] = j;
        for (int i = 1; i <= m; ++i)
            dp[i][0] = i;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else 
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
        return dp[m][n];
    }
}

647. 回文子串

优质题解

二刷看的题解

状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。 状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false 这个状态转移方程是什么意思呢？

当只有一个字符时，比如 a 自然是一个回文串。 当有两个字符时，如果是相等的，比如 aa，也是一个回文串。 当有三个及以上字符时，比如 ababa 这个字符记作串 1，把两边的 a 去掉，也就是 bab 记作串 2，可以看出只要串2是一个回文串，那么左右各多了一个 a 的串 1 必定也是回文串。所以当 s[i]==s[j] 时，自然要看 dp[i+1][j-1] 是不是一个回文串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int countSubstrings(String s) {
        // dp[i][j]: s[i:j]的回文子串个数
        int n = s.length(), res = 0;
        boolean[][] dp = new boolean[n][n];
        for (int j = 0; j < n; ++j)  
            for (int i = 0; i <= j; ++i) 
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    ++res;
                }
        return res;
    }
}

换一种遍历顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int countSubstrings(String s) {
        // dp[i][j]: s[i:j]的回文子串个数
        int n = s.length(), res = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; --i)  
            for (int j = i; j < n; ++j) 
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    ++res;
                }
        return res;
    }
}

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int countSubstrings(String s) {
        int n = s.length(), res = 0;
        boolean[][] dp = new boolean[n][n];
        for (int j = 0; j < n; ++j) {
            for (int i = j; i >= 0; --i) {
                if (i == j)
                    dp[i][j] = true;
                else if (i + 1 == j)
                    dp[i][j] = s.charAt(i) == s.charAt(j) ? true : false;
                else {
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
                }
                if (dp[i][j])
                    ++res;
            }
        }
        return res;
    }
}

5. 最长回文子串

方法一：DP

dp[i][j] = ch1 == ch2 && (dp[i + 1][j - 1] || j - i + 1 <= 2) 从最后一行开始遍历，从左往右、从右往左都可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String longestPalindrome(String s) {
        // dp[i][j] = ch1 == ch2 && (dp[i + 1][j - 1] || j - i + 1 <= 2)
        // dp[i][j]: s[i:j]是否是回文串
        int n = s.length(),l = 0, r = 0, maxLen = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; --i) {
            // for (int j = n - 1; j >= i; --j) 也可以
            for (int j = i; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j) && (j - i + 1 <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        l = i;
                        r = j;
                    }
                }
            }
        }
        return s.substring(l, r + 1);        
    }
}

516. 最长回文子序列

方法一：DP

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
class Solution {
    public int longestPalindromeSubseq(String s) {
//        dp[i][j]: 字符串从下标i到j的最长回文子序列
//        dp[i][j]:
//        s[i] == s[j]: d[i + 1][j - 1]
//        s[i] != s[j]: max(dp[i + 1][j], dp[i][j - 1])
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int j = 0; j < n; ++j) {
            for (int i = j; i >= 0; --i) {
                if (i == j)
                    dp[i][j] = 1;
                else if (i + 1 == j)
                    dp[i][j] = s.charAt(i) == s.charAt(j) ? 2 : 1;
                else {
                    if (s.charAt(i) == s.charAt(j))
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    else
                        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

二刷

dp[i][j - 1] dp[i][j]
dp[i + 1][j - 1] dp[i + 1][j]
  1. 从下往上，从左往右遍历
  2. else if (s.charAt(i) == s.charAt(j))一定要else if不能是if。如果是if会越界(i = n - 1时, dp[i + 1][j - 1]越界)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (i == j)
                    dp[i][j] = 1;
                else if (s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else 
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
}

剑指 Offer II 092. 翻转字符

注意：(ch == '1' ? 0 : 1)的括号

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minFlipsMonoIncr(String s) {
        // dp[i][0]: 经过若干转换使得子串s[:i]有序且最后一位是0的最少翻转次数
        // dp[i][1]：经过若干转换使得子串s[:i]有序且最后一位是1的最少翻转次数
        /* 状态转移：dp[i][0] = dp[i - 1][0] + s[i] == 0 ? 0 : 1;
                    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + s[i] == 1 ? 0 : 1;
            初始化：dp[0][0] = s[0] == 0 ? 0 : 1;
                   dp[0][1] = s[0] == 1 ? 0 : 1;
         */
         int[][] dp = new int[s.length()][2];
         dp[0][0] = s.charAt(0) == '0' ? 0 : 1;
         dp[0][1] = s.charAt(0) == '1' ? 0 : 1;
         for (int i = 1; i < s.length(); ++i) {
             char ch = s.charAt(i);
             dp[i][0] = dp[i - 1][0] + (ch == '0' ? 0 : 1);
             dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + (ch == '1' ? 0 : 1); 
         }
         return Math.min(dp[s.length() - 1][0], dp[s.length() - 1][1]);
    }
}

剑指 Offer II 093. 最长斐波那契数列

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0; i < n; ++i)
            map.put(arr[i], i);
        for (int i = 2; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                int k = map.getOrDefault(arr[i] - arr[j], -1);
                if (k >= 0 && k < j)
                    dp[j][i] = Math.max(dp[k][j] + 1, 3);
                res = Math.max(res, dp[j][i]);
            }
        }
        return res;
    }
}

分割回文串 II

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
class Solution {
    public int minCut(String s) {
        int n = s.length();
        /**
        i < j && s[i] == s[j], dp[i][j] = dp[i + 1][j - 1]
         */
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; --i) 
            for (int j = i; j < n; ++j) 
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1]))
                    dp[i][j] = true;
        /**
        if (dp[0][n - 1]) return 0;
        if (dp[i][j])
         */
        int[] memo = new int[n];
        for (int i = 0; i < n; ++i) {
            if (dp[0][i])
                memo[i] = 0;
            else {
                memo[i] = i;
                for (int j = 1; j <= i; ++j) {
                    if (dp[j][i]) 
                        memo[i] = Math.min(memo[i], memo[j - 1] + 1);
                }
            }
        }
        return memo[n - 1];
    }
}

剑指 Offer II 096. 字符串交织

初始化出错了，debug半天

1
2
3
4
for (int i = 1; i <= n && s2.charAt(i - 1) == s3.charAt(i - 1); ++i) // 不符合提前终止for循环
            dp[0][i] = true;
for (int i = 1; i <= m && s1.charAt(i - 1) == s3.charAt(i - 1); ++i)
    dp[i][0] = true;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length(), t = s3.length();
        if (t != m + n)
            return false;
        // dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]) || (s2[j] == s3[i + j] && dp[i][j - 1])
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n && s2.charAt(i - 1) == s3.charAt(i - 1); ++i)
            dp[0][i] = true;
        for (int i = 1; i <= m && s1.charAt(i - 1) == s3.charAt(i - 1); ++i)
            dp[i][0] = true;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                if ((s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j]) || (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]))
                    dp[i][j] = true;
        return dp[m][n];
    }
}

115. 不同的子序列

二刷记忆化搜索

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
class Solution {
    public int numDistinct(String s, String t) {
        m = s.length();
        n = t.length();
        this.s = s;
        this.t = t;
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    public int dfs(int i, int j) {
        // t被匹配返回1
        if (j == n)
            return 1;
        // s到最后也没能匹配到t的最后一个字符，返回0
        if (i == m)
            return 0;
        if (dp[i][j] != -1)
            return dp[i][j];
        // 匹配：选：i，j往下递归；不选：i往下递归
        if (s.charAt(i) == t.charAt(j))
            return dp[i][j] = dfs(i + 1, j + 1) + dfs(i + 1, j);
        return dp[i][j] = dfs(i + 1, j);
    }

    int m, n;
    String s, t;
    int[][] dp;
}

方法三：滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        // s[:i]中t[:j]出现的次数
        int[] dp = new int[n + 1];
        // s,t为空串，匹配
        dp[0] = 1; 
        for (int i = 1; i <= m; ++i) {
            for (int j = n; j >= 1; --j) {
                if (s.charAt(i - 1) == t.charAt(j - 1))
                    dp[j] += dp[j - 1];
            }
        }
        return dp[n];
    }
}

方法一：DP

注意初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int numDistinct(String s, String t) {
        /**
        s = "bagg", t = "bag"
        对于bag的最后一个'g'，可以使用它，或者不使用它
         */
         int m = s.length(), n = t.length();
        if (m < n)
            return 0;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1;i <= m; ++i)
            dp[i][0] = 1;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s.charAt(i - 1) == t.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[m][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
class Solution {
    public int numDistinct(String s, String t) {
        m = s.length();
        n = t.length();
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(s, t, m - 1, n - 1);
    }

    int m, n;
    int[][] dp;

    private int dfs(String s, String t, int i, int j) {
        if (j < 0)	// base case 当j指针越界，此时t为空串，s不管是不是空串，匹配方式数都是1
            return 1;
        if (i < 0)	// base case i指针越界，此时s为空串，t不是，s怎么也匹配不了t，方式数0
            return 0;
        if (dp[i][j] != -1)
            return dp[i][j];
        if (s.charAt(i) == t.charAt(j))
            return dp[i][j] = dfs(s, t, i - 1, j - 1) + dfs(s, t, i - 1, j);
        else
            return dp[i][j] = dfs(s, t, i - 1, j);
    }
}

392. 判断子序列

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isSubsequence(String s, String t) {
        /**
        dp[i][j]:s[:i]是否是t[:j]的子序列
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] && s[i] == t[j]
        初始化：s为空，都是t的子串
         */
         int m = s.length(), n = t.length();
         boolean[][] dp = new boolean[m + 1][n + 1];
         for (int j = 0; j <= n; ++j) 
            dp[0][j] = true;
        for (int i = 1; i <= m; ++i) 
            for (int j = 1; j <= n; ++j) 
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] && s.charAt(i - 1) == t.charAt(j - 1);
        return dp[m][n];
    }
}

销售利润最大化

方法一：线性DP

相似题目 - 2008. 出租车的最大盈利（和本题几乎一样）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        List<int[]>[] list = new List[n];
        Arrays.setAll(list, e -> new ArrayList<>());
        for (List<Integer> offer : offers) {
            int start = offer.get(0), end = offer.get(1), val = offer.get(2);
            list[end].add(new int[]{start, val});
        }
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            for (int[] arr : list[i - 1]) {
                int start = arr[0], val = arr[1];
                dp[i] = Math.max(dp[i], dp[start] + val);
            }
        }
        return dp[n];
    }
}

方法二：二分 + DP

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
class Solution {
    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        Collections.sort(offers, (o1, o2) -> o1.get(1) - o2.get(1));
        // 处理标号为0~i的房子能获得的最大利润
        int[] dp = new int[offers.size() + 1];
        for (int i = 0; i < offers.size(); ++i) {
            dp[i + 1] = dp[i];
            int j = bisearch(offers, i, offers.get(i).get(0));
            dp[i + 1] = Math.max(dp[i + 1], (j >= -1 ? dp[j + 1] : 0) + offers.get(i).get(2));
        }
        return dp[offers.size()];
    }

    private int bisearch(List<List<Integer>> offers, int r, int start) {
        int l = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (offers.get(mid).get(1) < start)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;
    }
}

2008. 出租车的最大盈利

方法一：线性DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
        List<int[]>[] list = new List[n + 1];
        Arrays.setAll(list, o -> new ArrayList<>());
        for (int[] ride : rides) {
            int from = ride[0], to = ride[1], tips = ride[2];
            list[to].add(new int[]{from, to - from + tips});
        }
        long[] dp = new long[n + 1];
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            for (int[] arr : list[i]) {
                int start = arr[0], val = arr[1];
                dp[i] = Math.max(dp[i], dp[start] + val);
            }
        }
        return dp[n];
    }
}

1235. 规划兼职工作

数据量\(10^9\)，如果用上述方法存储，会爆内存

方法一：二分 + DP

  • 将jobs按照结束时间排序，dp[i]：处理前i分工作(做或者不做)能获得的最大利润，dp[0]没有意义(防止溢出)
  • 对于第i份兼职，可以不做dp[i] = dp[i - 1]，或者做dp[i] = dp[j + 1] + prof，其中j是满足jobs[j][1] <= jobs[i][0]的最大下标(dp数组是非递减的)，可以使用二分来找到j
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
class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; ++i) {
            jobs[i][0] = startTime[i];
            jobs[i][1] = endTime[i];
            jobs[i][2] = profit[i];
        }
        Arrays.sort(jobs, (o1, o2) -> o1[1] - o2[1]);
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            int start = jobs[i - 1][0], end = jobs[i - 1][1], p = jobs[i - 1][2];
            int j = bisearch(jobs, i, start); // 右边界是i，找到最大的下标j，jobs[j][1] <= start
            dp[i] = Math.max(dp[i], dp[j + 1] + p); // dp数组下标都往后移一位
        }
        return dp[n];
    }

    private int bisearch(int[][] jobs, int r, int start) {
        int l = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (jobs[mid][1] <= start)
                l = mid + 1;
            else 
                r = mid - 1;
        }
        return r;
    }
}

1751. 最多可以参加的会议数目 II

数量限制

方法一：二分 + 二维DP

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 maxValue(int[][] events, int k) {
        Arrays.sort(events, (o1, o2) -> o1[1] - o2[1]);
        int n = events.length;
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 0; i < n; ++i) {
            int p = bisearch(events, i, events[i][0]);
            for (int j = 1; j <= k; ++j) {
                dp[i + 1][j] = Math.max(dp[i][j], dp[p + 1][j - 1] + events[i][2]);
            }
        }
        return dp[n][k];
    }

    private int bisearch(int[][] events, int r, int start) {
        int l = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (events[mid][1] < start)
                l = mid + 1;
            else 
                r = mid - 1;
        }
        return r;
    }
}

2054. 两个最好的不重叠活动

方法一：二分查找 + 线性dp

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 maxTwoEvents(int[][] events) {
        int n = events.length;
        Arrays.sort(events, (o1, o2) -> o1[1] - o2[1]);
        int[][] dp = new int[n + 1][3];
        for (int i = 0; i < n; ++i) {
            int p = bisearch(events, i, events[i][0]);
            for (int j = 1; j <= 2; ++j) {
                dp[i + 1][j] = Math.max(dp[i][j], dp[p + 1][j - 1] + events[i][2]);
            }
        }
        return dp[n][2];
    }

    private int bisearch(int[][] events, int r, int start) {
        int l = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (events[mid][1] < start)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;
    }
}

剑指 Offer 47. 礼物的最大价值

方法一：记忆化搜索

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
class Solution {
    public int maxValue(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    private int dfs(int i, int j) {
        if (i == m && j == n)
            return 0;
        if (dp[i][j] != -1)
            return dp[i][j];
        int res = grid[i][j], max = 0;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col)) {
                max = Math.max(max, dfs(row, col));
            }
        }
        res += max;
        return dp[i][j] = res;
    }

    private boolean isValid(int i, int j) {
        return i < m && j < n;
    }

    int[][] grid, dirs = new int[][]{{1, 0}, {0, 1}}, dp;
    int m, 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
class Solution {
    public int maxValue(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    private int dfs(int i, int j) {
        if (i >= m || j >= n)
            return 0;
        if (dp[i][j] != -1)
            return dp[i][j];
        return dp[i][j] = Math.max(dfs(i + 1, j), dfs(i, j + 1)) + grid[i][j];
    }

    private boolean isValid(int i, int j) {
        return i < m && j < n;
    }

    int[][] grid, dp;
    int m, n;
}

方法三：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxValue(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        dp = new int[m + 1][n + 1];
        for (int i = 0; i < m; ++i) 
            for (int j = 0; j < n; ++j) 
                dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]) + grid[i][j];
        return dp[m][n];
    }

    int[][] grid,  dp;
    int m, n;
}

方法四：DP + 滚动数组

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n + 1];
        for (int i = 0; i < m; ++i)
            for (int j =0; j < n; ++j)
                dp[j + 1] = grid[i][j] + Math.max(dp[j + 1], dp[j]);
        return dp[n];
    }
}

931. 下降路径最小和

方法一：记忆化搜索

注意初始化dp数组

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
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        this.matrix = matrix;
        n = matrix.length;
        int res = Integer.MAX_VALUE;
        dp = new int[n][n];
        for (int[] arr : dp)
            Arrays.fill(arr, Integer.MAX_VALUE);
        for (int i = 0; i < n; ++i) {
            res = Math.min(res, dfs(0, i));
        }
        return res;
    }

    private int dfs(int i, int j) {
        if (i == n)
            return 0;
        if (dp[i][j] != Integer.MAX_VALUE)
            return dp[i][j];
        int l = j > 0 ? dfs(i + 1, j - 1) : Integer.MAX_VALUE;
        int d = dfs(i + 1, j);
        int r = j < n - 1 ? dfs(i + 1, j + 1) : Integer.MAX_VALUE;
        return dp[i][j] = Math.min(l, Math.min(d,  r)) + matrix[i][j];
    }

    int[][] matrix, dp;
    int 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
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        this.matrix = matrix;
        n = matrix.length;
        int res = Integer.MAX_VALUE;
        dp = new int[n][n];
        for (int[] arr : dp)
            Arrays.fill(arr, Integer.MAX_VALUE);
        for (int i = 0; i < n; ++i) {
            res = Math.min(res, dfs(0, i));
        }
        return res;
    }

    private int dfs(int i, int j) {
        if (i == n)
            return 0;
        if (j < 0 || j == n)
            return Integer.MAX_VALUE;
        if (dp[i][j] != Integer.MAX_VALUE)
            return dp[i][j];
        return dp[i][j] = Math.min(dfs(i + 1, j - 1), Math.min(dfs(i + 1, j),  dfs(i + 1, j + 1))) + matrix[i][j];
    }

    int[][] matrix, dp;
    int n;
}

方法三：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n + 1][n + 2];
        for (int i = 0; i <= n; ++i) {
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][n + 1] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < n; ++j) 
                dp[i + 1][j + 1] = matrix[i][j] + Math.min(dp[i][j], Math.min(dp[i][j + 1], dp[i][j + 2]));
        int res = Integer.MAX_VALUE;
        for (int j = 1; j <= n; ++j)
            res = Math.min(res, dp[n][j]);
        return res;
    }
}

方法四：滚动数组

用pre记录左上角的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[] dp = new int[n + 2];
        dp[0] = Integer.MAX_VALUE;
        dp[n + 1] = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i)
            dp[i + 1] = matrix[0][i];
        for (int i = 1; i < n; ++i) {
            int pre = dp[0];
            for (int j = 0; j < n; ++j) {
                int temp = pre;
                pre = dp[j + 1];
                dp[j + 1] = matrix[i][j] + Math.min(temp, Math.min(pre, dp[j + 2]));
            }
        }
        int res = Integer.MAX_VALUE;
        for (int j = 1; j <= n; ++j)
            res = Math.min(res, dp[j]);
        return res;
    }
}

1262. 可被三整除的最大和

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxSumDivThree(int[] nums) {
        this.nums=  nums;
        n = nums.length;
        dp = new int[n][3];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    private int dfs(int index, int sum) {
        if (index == n)
            return sum == 0 ? 0 : Integer.MIN_VALUE;
        if (dp[index][sum] != -1)
            return dp[index][sum];
        return dp[index][sum] = Math.max(dfs(index + 1, sum), dfs(index + 1, (sum + nums[index]) % 3) + nums[index]);
    }

    int[] nums;
    int n;
    int[][] dp;
}

918. 环形子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int maxSubarraySumCircular(int[] A) {
    int total = 0, maxSum = A[0], curMax = 0, minSum = A[0], curMin = 0;
    for (int a : A) {
        curMax = Math.max(curMax + a, a);
        maxSum = Math.max(maxSum, curMax);
        curMin = Math.min(curMin + a, a);
        minSum = Math.min(minSum, curMin);
        total += a;
    }
    return minSum != total ? Math.max(maxSum, total - minSum) : maxSum;
}
}

1186. 删除一次得到子数组最大和

方法四：二刷

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
class Solution {
    public int maximumSum(int[] arr) {
        nums = arr;
        n = arr.length;
        dp = new int[n][2][2];
        for (int[][] a : dp)
            for (int[] b : a)
                Arrays.fill(b, -10001);
        return dfs(0, 1, false);
    }

    private int dfs(int index, int key, boolean chosen) {
        if (index == n)
            return chosen ? 0 : Integer.MIN_VALUE;
        if (dp[index][key][chosen ? 1 : 0] != -10001)
            return dp[index][key][chosen ? 1 : 0];
        int pass;
        if (chosen) 
            pass = 0;
        else
            pass = dfs(index + 1, key, false);
        int choose = dfs(index + 1, key, true) + nums[index], delete = Integer.MIN_VALUE;
        if (key == 1) 
            delete = dfs(index + 1, 0, chosen);
        int max = Math.max(Math.max(pass, choose), delete);
        res = Math.max(res, max);
        return dp[index][key][chosen ? 1 : 0] = max;
    }

    int[] nums;
    int n;
    int res = Integer.MIN_VALUE;
    int[][][] dp;
}

方法一：记忆化搜索

由于至少要选一个元素，不能是空数组，所以复杂特别多

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
class Solution {
    public int maximumSum(int[] arr) {
        nums = arr;
        n = nums.length;
        dp = new int[n][2][2];
        for (int[][] x : dp)
            for (int[] y : x)
                Arrays.fill(y, Integer.MIN_VALUE);
        return dfs(0, 1, false, false);
    }

    // 选x或者不选
    // 如果选，之后的数可以选择删或者不删
    // 至少要选一个
    // PASS有两种情况：1.前面没选pass；2.选了，后面都pass
    private int dfs(int index, int key, boolean hasChosen, boolean stop) {
        if (stop)
            return 0;
        if (index == n)
            return hasChosen ? 0 : Integer.MIN_VALUE;
        if (dp[index][key][hasChosen ? 1 : 0] != Integer.MIN_VALUE)
            return dp[index][key][hasChosen ? 1 : 0];
        int pass = Integer.MIN_VALUE, delete = Integer.MIN_VALUE, choose = Integer.MIN_VALUE;
        int chooseStop = Integer.MIN_VALUE, deleteStop = Integer.MIN_VALUE;
        if (!hasChosen)
            pass = dfs(index + 1, key, hasChosen, false);
        choose = dfs(index + 1, key, true, false) + nums[index];
        chooseStop = dfs(index + 1, key, true, true) + nums[index];
        if (hasChosen && key >= 1) {
            delete = dfs(index + 1, 0, true, false);
            deleteStop = dfs(index + 1, 0, true, true);
        }
        int temp = Math.max(pass, Math.max(choose, delete));
        temp = Math.max(temp, Math.max(chooseStop, deleteStop));
        res = Math.max(res, temp);
        return dp[index][key][hasChosen ? 1 : 0] = temp;
    }

    int[][][] dp;
    int[] nums;
    int n, res = Integer.MIN_VALUE;
}

方法二：记忆化搜索

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
class Solution {
    public int maximumSum(int[] arr) {
        nums = arr;
        n = arr.length;
        dp = new int[n][2];
        for (int[] x : dp)
            Arrays.fill(x, Integer.MIN_VALUE);
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; ++i)
            res = Math.max(res, Math.max(dfs(i, 0), dfs(i, 1)));
        return res;
    }

    private int dfs(int i, int j) {
        if (i == n)
            return Integer.MIN_VALUE >> 1;
        if (dp[i][j] != Integer.MIN_VALUE)
            return dp[i][j];
        if (j == 0)
            return dp[i][j] = Math.max(dfs(i + 1, 0), 0) + nums[i];
        return dp[i][j] = Math.max(dfs(i + 1, 1) + nums[i], dfs(i + 1, 0));
    }

    int[][] dp;
    int[] nums;
    int n, res = Integer.MIN_VALUE;
}

方法三：1:1转换DP

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maximumSum(int[] nums) {
        int n = nums.length, res = Integer.MIN_VALUE;
        int[][] dp = new int[n + 1][2];
        Arrays.fill(dp[0], Integer.MIN_VALUE >> 1); // if (i == n) return Integer.MIN_VALUE >> 1;
        for (int i = 0; i < n; ++i) {
            dp[i + 1][0] = Math.max(dp[i][0], 0) + nums[i];
            dp[i + 1][1] = Math.max(dp[i][1] + nums[i], dp[i][0]);
            res = Math.max(res, Math.max(dp[i + 1][0], dp[i + 1][1]));
        }
        return res;
    }
}

Algorithms > Dynamic Programming
#动态规划
Dynamic Programming
https://leopol1d.github.io/2023/05/27/dynamic-programming/
作者
Leopold
发布于
2023年5月27日
许可协议