线性动态规划

最小路径和

class Solution {
    public static int minPathSum(int[][] grid) {
        int dp[][]=new int[grid.length][grid[0].length];
        dp[0][0]=grid[0][0];
        for(int i=1;i<grid[0].length;i++){
            dp[0][i]=grid[0][i]+dp[0][i-1];
        }
        for(int i=1;i<grid.length;i++){
            dp[i][0]=grid[i][0]+dp[i-1][0];
        }
        for(int i=1;i< grid.length;i++){
            for(int j=1;j<grid[i].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];
    }
}

初始化第一行和第一列，除了第一行第一列，其他的每个位置继承上/左的距离，选择最短的那个即可。 

不同路径Ⅱ

import java.util.Arrays;
class Solution {
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int dp[][] = new int[obstacleGrid.length][obstacleGrid[0].length];
        for (int i = 0; i < obstacleGrid.length; i++) {
            for (int j = 0; j < obstacleGrid[0].length; j++) {
                if (i == 0 && j == 0 && obstacleGrid[i][j] != 1) {
                    dp[i][j] = 1;
                    continue;
                }
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    try {
                        dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
                    } catch (Exception e) {
                        try {
                            dp[i][j] += dp[i][j - 1];
                        } catch (Exception k) {
                            dp[i][j] += dp[i - 1][j];
                        }
                    }

                }
            }
        }
        return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }
}

判断，嵌套...

三角形最小路径和

数塔问题

class Solution {
    public static int minimumTotal(List<List<Integer>> triangle) {
        int f[][] = new int[triangle.size()][triangle.get(triangle.size() - 1).size()];

        // 初始值 f[i][j] 4 1 8 3
        for (int i = 0; i < triangle.get(triangle.size() - 1).size(); i++) {
            f[triangle.size() - 1][i] = triangle.get(triangle.size() - 1).get(i);
        }
        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                try {
                    f[i][j] += Math.min(f[i + 1][j], f[i + 1][j + 1]) + triangle.get(i).get(j);
                } catch (Exception e) {
                    f[i][j] = triangle.get(i).get(j);
                }
            }
        }
        return f[0][0];
    }
}

下降路径最小和 

class Solution {
    public static void main(String[] args) {
        System.out.println(minFallingPathSum(new int[][]{{2, 1, 3}, {6, 5, 4}, {7, 8, 9}}));
    }

    public static int minFallingPathSum(int[][] matrix) {
        int f[][] = new int[matrix.length][matrix[0].length + 2];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length + 2; j++) {
                f[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 1; i <= matrix[0].length; i++) {
            f[matrix.length - 1][i] = matrix[matrix.length - 1][i - 1];
        }
        for (int i = matrix.length - 2; i >= 0; i--) {
            for (int j = 1; j <= matrix[0].length; j++) {
                f[i][j] = Math.min(f[i + 1][j], Math.min(f[i + 1][j + 1], f[i + 1][j - 1])) + matrix[i][j - 1];
            }
        }
        int minv = Integer.MAX_VALUE;
        for (int i = 1; i <= matrix[0].length; i++) {
            minv = Math.min(minv, f[0][i]);
        }
        return minv;
    }
}