Acwing典中典系列

普通数字三角形

正方形数三dp 摘花生

正方形数三dp 最低通行费

多路径数三dp 方格取数

多路径数三dp 传纸条

记忆化搜索dp 滑雪

LeetCode

64. 最小路径和

思路：

正常的三角形思路，但是我们能如何优化呢？

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         //数字三角形
  4.         int m = grid.length, n = grid[0].length;
  5.         int[][] f = new int[m + 1][n + 1];
  7.         f[0][1] = 0; f[1][0] = 0;
  8.         for (int i = 1; i <= m; i ++){
  9.             if (i > 1)
  10.                 f[i][0] = Integer.MAX_VALUE;
  11.             for (int j = 1; j <= n; j++){
  12.                 if (j > 1)
  13.                     f[0][j] = Integer.MAX_VALUE;
  14.                 f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i - 1][j - 1];
  15.             }
  16.         }
  17.         return f[m][n];
  18.     }
  19. }

典中典120. 三角形最小路径和

思路1

经典的数字三角形问题，时间复杂度o(n^2), 空间复杂度o(n^2)

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

思路2 优化空间复杂度到o(1)

  1. class Solution {
  2.     public int minimumTotal(List<List<Integer>> triangle) {
  3.         int m = triangle.size(), n = triangle.get(m - 1).size();
  4.         for (int i = m - 2; i >= 0; i--){
  5.             for (int j = i; j >= 0; j--){
  6.                 int tmp = Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)) + triangle.get(i).get(j);
  7.                 triangle.get(i).set(j, tmp); 
  8.             }
  9.         }
  10.         return triangle.get(0).get(0);
  11.     }
  12. }

329. 矩阵中的最长递增路径 记忆化搜索

思路：

和滑雪一模一样，记忆化搜索dp

  1. class Solution {
  2.     int[] dx = new int[]{0, -1, 0, 1};
  3.     int[] dy = new int[]{-1, 0, 1, 0}; 
  4.     int[][] f;
  5.     int m, n;
  6.     public int longestIncreasingPath(int[][] matrix) {
  7.         //记忆化搜索dp， 由于f[i,j] 依赖于f[i , j  + 1]，需要先搜索把f[i, j + 1]计算出来
  8.         m = matrix.length; n = matrix[0].length;
  9.         f = new int[m][n];
  10.         for (int i = 0; i < m; i ++)
  11.             Arrays.fill(f[i], -1);
  12.         int res = Integer.MIN_VALUE;
  13.         for (int i = 0; i < m; i ++){
  14.             for (int j = 0; j < n; j ++){
  15.                 res = Math.max(res, dp(i, j, matrix));
  16.             }
  17.         }
  18.         return res;
  19.     }
  21.     public int dp(int x, int y, int[][] matrix){
  22.         if (f[x][y] != -1) return f[x][y];
  23.         f[x][y] = 1;
  24.         for (int i = 0; i < 4; i ++){
  25.             int nx = dx[i] + x, ny = dy[i] + y;
  26.             if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
  27.             if (matrix[nx][ny] > matrix[x][y])
  28.                 f[x][y] = Math.max(f[x][y], dp(nx, ny, matrix) + 1);
  29.         }
  30.         return f[x][y];
  31.     }
  32. }

576. 出界的路径数 记忆化搜索

思路

记忆化搜索，但是超时了

76 / 94 个通过测试用例 超出时间限制

  1. class Solution {
  2.     int n, m;
  3.     int limit;
  4.     boolean[][][] f;
  5.     int mod =(int)(1e9) + 7;
  6.     int[] dx = new int[]{0, -1, 0, 1}, dy = new int[]{-1, 0, 1, 0};
  7.     public int findPaths(int m, int n, int N, int i, int j) {
  8.         //类似于记忆化搜索？
  9.         //f[i][j] 表示ij起点 移出边界的最大数量 =一步移除边界+ 周围点最大数量
  10.         f = new boolean[m][n][N];
  11.         limit = N; this.n = n; this.m = m;
  12.         return dp(i, j, 1);
  13.     }
  15.     public int dp(int x, int y, int step){
  16.         int count = 0;
  17.         if (step > limit) return count;
  18.         f[x][y][step - 1] = true;
  19.         for (int i = 0; i < 4; i ++){
  20.             int nx = x + dx[i]; int ny = y + dy[i];
  21.             if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
  22.                 count++;continue;
  23.             }
  24.             if (f[nx][ny][step - 1] == true)continue;
  25.             count = (count + dp(nx, ny, step + 1)) % mod;
  26.         }
  27.       //  System.out.println(x + " " + y + " " + "count :" +  count + " " + "step :" + step);
  28.         return count;
  29.     }
  30. }

倒序dp 174. 地下城游戏

由于这道题中的骑士向后走要依赖于后面一个关卡的消耗的血量。

因此实际上dp[i][j]:只能定义为从 (i,j)出发，到达终点需要的最小血量。

这就要求了，必须从右下向左上dp。

转移方程数字三角形 - 图1-dungeon%5Bi%5D%5Bj%5D%2C%201)#card=math&code=f%5Bi%5D%5Bj%5D%20%3D%20max%28min%28f%5Bi%2B1%5D%5Bj%5D%2C%20f%5Bi%5D%5Bj%2B1%5D%29-dungeon%5Bi%5D%5Bj%5D%2C%201%29)(每一关骑士的血量必须>=1)

f[m][n] = 1

class Solution {
    public int calculateMinimumHP(int[][] d) {
        int m = d.length;
        if (m == 0) return 1;
        int n = d[0].length;
        int[][] f = new int[m+1][n+1];
        for (int i = 0; i <= n; i ++)
            f[m][i] =Integer.MAX_VALUE;
        for (int i = 0; i <= m; i ++)
            f[i][n] = Integer.MAX_VALUE;
        f[m][n - 1] = 1; f[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; i --){
            for (int j = n - 1; j >= 0; j--){
                f[i][j] = Math.max(Math.min(f[i][j + 1], f[i + 1][j]) - d[i][j], 1);
                //System.out.println(i + " " + j + " " + f[i][j]);
            }
        }
        return f[0][0];
    }
}