image.png

二维 动态规划

  1. public int minPathSum (int[][] matrix) {
  2.         // write code here
  3.         int m = matrix.length;
  4.         int n = matrix[0].length;
  5.         int[][] dp = new int[m][n];
  6.         dp[0][0] = matrix[0][0];
  7.         for(int i = 1; i < m; i++)
  8.             dp[i][0] = matrix[i][0]+dp[i-1][0];
  9.         for(int i = 1; i < n; i++)
  10.             dp[0][i] = matrix[0][i]+dp[0][i-1];
  11.         for(int i = 1; i < m; i++){
  12.             for(int j = 1; j < n; j++){
  13.                 dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);
  14.             }
  15.         }
  16.         return dp[m-1][n-1];
  17.     }

降维

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