Java-LeetCode64. 最小路径和-动态规划

• 算法
  • 1.动态规划：dp[i][j]表示(0,0)到(i,j)位置的最小路径和
  • 2.初始状态：dp[i][0] = dp[i-1][0] + matrix[i][0]；dp[0][i] = dp[0][i-1] + matrix[0][i]
  • 3.过渡公式：dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]；到(i,j)的最小路径和等于上方和左方的较小路径和加上当前位置值

public int minPathSum(int[][] matrix) {
    int row = matrix.length;
    int col = matrix[0].length;
    int[][] dp = new int[row][col];
    dp[0][0] = matrix[0][0];
    for (int i = 1; i < row; i++) {
        dp[i][0] = dp[i-1][0] + matrix[i][0];
    }
    for (int i = 1; i < col; i++) {
        dp[0][i] = dp[0][i-1] + matrix[0][i];
    }
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i][j];
        }
    }
    return dp[row-1][col-1];
}

• 算法
  • 1.优化空间复杂度
  • 2.顺序更新不需要中间变量

public int minPathSum(int[][] matrix) {
    int row = matrix.length;
    int col = matrix[0].length;
    int[] dp = new int[col];
    dp[0] = matrix[0][0];
    for (int i = 1; i < col; i++) {
        dp[i] = dp[i-1] + matrix[0][i];
    }
    for (int i = 1; i < row; i++) {
        dp[0] = dp[0] + matrix[i][0];
        for (int j = 1; j < col; j++) {
            dp[j] = Math.min(dp[j], dp[j-1]) + matrix[i][j];
        }
    }
    return dp[col-1];
}