九章算法题解记录【四】动态规划I

动态规划四种类型
1 Matrix DP 10%
2 Sequence 40%
3 TwoSequence 40%
4 Backpack 10%

四点要素：
1 定义状态含义
2 方程（倒数第一步）
3 初始化如：f[0] = 0
4 答案如：返回 f[n]

第一大类： 2D-Matrix
state: f[x][y] 表示我从起点走到坐标x,y……
function: 研究走到x,y这个点之前的一步
intialize: 起点
answer: 终点

Triangle https://www.lintcode.com/problem/triangle/

public class Solution {
 /**
  * @param triangle: a list of lists of integers
  * @return: An integer, minimum path sum
  */
 public int minimumTotal(int[][] triangle) {
     // 状态定义 dp[i][j] i j位置的最短路径和
     if (triangle == null) return 0;
     int height = triangle.length;
     int[][] dp = new int[height][height];

     // 初始化
     dp[0][0] = triangle[0][0];
     for (int i = 1; i < height; i++) {
         dp[i][0] = triangle[i][0] + dp[i - 1][0];
         dp[i][i] = triangle[i][i] + dp[i - 1][i - 1];
     }

     // 递归求解
     for (int i = 1; i < height; i++) {
         for (int j = 1; j < i; j++) {
             dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
         }
     }
     // 答案
     int min = Integer.MAX_VALUE;
     for (int i = 0; i < height; i++) {
         min = Math.min(min, dp[height - 1][i]);
     }
     return min;
 }
}

一遍AC，稍微改了一下初始化条件。
解题思路：按照DP四步走。第一种 2D-Matrix

2 Minimum Path Sum http://www.lintcode.com/problem/minimum-path-sum/

public class Solution {
    /**
     * @param grid: a list of lists of integers
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    public int minPathSum(int[][] grid) {
        // 错误输入条件
        if (grid == null || grid[0] == null){
            return 0;
        }
        // 状态定义 dp[i][j]表示在i j点此时的最短路径和
        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] = grid[i][0] + dp[i - 1][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++) {
            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];
    }
}

解题思路 2D-Matrix 四步走一遍AC

Unique Paths https://www.lintcode.com/problem/unique-paths/description

public class Solution {
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) {
            return 0;
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = 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];
    }
}

解题思路：简单题，直接写答案了。可能会有贪心解，但不是练习目的。

4 UniquePathII 上一题的变式 http://www.lintcode.com/problem/unique-paths-ii/

public class Solution {
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 上一题的变式，增加了一个同样大小的障碍物矩阵

        // 错误输入条件
        if (obstacleGrid == null || obstacleGrid[0] == null) return 0;
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        // 状态定义 dp[i][j]为i,j位置的路径数量
        int[][] dp = new int[m][n];

        // 初始化
        if (obstacleGrid[0][0] == 1){
            return 0;
        } else {
            dp[0][0] = 1;
        }
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] != 1){
                dp[i][0] = 1;
            }else {
                break;
            }
        }
        for (int i = 1; i < n; i++) {
            if (obstacleGrid[0][i] != 1){
                dp[0][i] = 1;
            }else {
                break;
            }
        }
        // 递归求解
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(obstacleGrid[i][j] != 1){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        // 答案
        return dp[m - 1][n - 1];

    }
}

解题思路:四步走，主要是在初始化与递归时判断条件，否则不变。 2D Matrix题一遍AC

第二大类：Sequence DP
state: f[i]表示“前i”个位置/数字/字母,(以第i个为)...
function: f[i] = f[j] … j 是i之前的一个位置
intialize: f[0]..
answer: f[n-1]..

5 Climbing Stairs

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // 错误输入条件
        if (n <= 0) return 0;

        // 状态定义 dp[i]指到达i时的方法个数
        int[] dp = new int[n+1];

        // 初始化
        dp[0] = 1;
        dp[1] = 1;

        // 递归求解
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // 答案
        return dp[n];
    }
}

解题思路：单序列dp 初始条件定义要好，不然会溢出一遍AC
感觉和2D-Matrix题差距不大，但是要定义好序列，注意指针不溢出

6 Jump Game http://www.lintcode.com/problem/jump-game/

public boolean canJump(int[] A) {
        // 错误输入条件
        if (A == null) return false;
        // 状态定义 boolean dp[i]表示i位置是否可达
        boolean[] dp = new boolean[A.length];

        // 初始化
        dp[0] = true;

        // 递归求解
        for (int i = 0; i < A.length - 1; i++) {
            if (dp[i]){
                for (int j = i; j < A.length && (j - i) <= A[i]; j++) {
                    dp[j] = true;
                }
            }
        }

        // 答案
        return dp[A.length - 1];
    }

解题方案：最优方法是贪心，尝试用dp写，发现一共有3个限制条件与各种越界危险，不能忽视！
越界判断尽量写得可读（j - i） <= A[i]这类，不用一定左边只放一个j。
本体Debug了很久，因为缺少限制条件或者错了边界。需要再刷。
感觉强行写成DP形式不太好，可以直接在j点往前遍历看能不能到j 。。也是O（n2）复杂度但好实现很多。。说明dp[i]定义很重要呀！
重新定义dp[i] = 站在i位置最多能到哪里

7 Jump Game II http://www.lintcode.com/problem/jump-game-ii/

public class Solution {
    /**
     * @param A: A list of integers
     * @return: An integer
     */
    public int jump(int[] A) {
        // 错误输入条件
        if (A == null) {
            return 0;
        }
        // 状态定义 dp[i]表示I处的最小次数
        int[] dp = new int[A.length];

        // 初始化
        dp[0] = 0;

        // 递归求解
        for (int i = 1; i < A.length; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = i - 1; j >= 0 ; j--) {
                if ((A[j] + j) >= i){
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        // 答案
        return dp[A.length - 1];
    }
}

解题思路：吸收了上题的教训，改变思路一遍AC，还是得多练。

第四课习题刷完了。养成固定套路，继续努力！