Java-算法-动态规划-附一

前置条件

        见Java-算法-动态规划

例一~例三

        见 Java-算法-动态规划

例四. leetcode62 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

（1）递归

以3，3为例给出递归的所有可能性

class Solution {
    public int uniquePaths(int m, int n) {
        return dfs(m,n);
    }
    public int dfs(int m, int n){
        if(m == 1 && n == 1){
            return 1;
        }
        if(m == 1 && n >1){
            return dfs(m,n-1);
        }
        if(n == 1 && m > 1){
            return dfs(m-1,n);
        }
        return dfs(m-1,n)+dfs(m,n-1);
    }
}

（2）记忆化搜索

显然有重复的递归操作，加上记忆化搜索

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] cache = new int[m+1][n+1];
        return dfs(m,n,cache);
    }
    public int dfs(int m, int n, int[][] cache){
        if(cache[m][n] != 0){
            return cache[m][n];
        }
        if(m == 1 && n == 1){
            return 1;
        }
        if(m == 1 && n >1){
            return dfs(m,n-1,cache);
        }
        if(n == 1 && m > 1){
            return dfs(m-1,n,cache);
        }
        int num = dfs(m-1,n,cache)+dfs(m,n-1,cache);
        cache[m][n] = num;
        return num;
    }
}

（3）动态规划

根据递推出动态规划表格

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = 1;
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j++){
                if(i == 0 || j == 0){
                    dp[i][j] = 1;
                }
                else{
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}

例五. leetcode53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int[] dp= new int[nums.length];
        dp[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

本题总结【1】：

• dp[i]：表示以 nums[i] 结尾的连续子数组的最大和。
• 以 1结尾的连续子数组有 [-2,1] 和 [1] ，其中 [-2,1] 就是在「子问题 1」的后面加上 1 得到。-2 + 1 = -1 < 1−2+1=−1<1 ，因此「子问题 2」 的答案是 1。
• 如果编号为 i 的子问题的结果是负数或者 0 ，那么编号为 i + 1 的子问题就可以把编号为 i 的子问题的结果舍弃掉，一个数 a 加上负数的结果比 a 更小；一个数 a 加上 00 的结果不会比 a 更大
• 而子问题的定义必须以一个数结尾，因此如果子问题 i 的结果是负数或者 0，那么子问题 i + 1 的答案就是以 nums[i] 结尾的那个数。

• 根据状态的定义，由于 nums[i] 一定会被选取，并且以 nums[i] 结尾的连续子数组与以 nums[i - 1] 结尾的连续子数组只相差一个元素 nums[i] 。

• 假设数组 nums 的值全都严格大于 0，那么一定有 dp[i] = dp[i - 1] + nums[i]。

• 可是 dp[i - 1] 有可能是负数，于是分类讨论：如果 dp[i - 1] > 0，那么可以把 nums[i] 直接接在 dp[i - 1] 表示的那个数组的后面，得到和更大的连续子数组；如果 dp[i - 1] <= 0，那么 nums[i] 加上前面的数 dp[i - 1] 以后值不会变大。于是 dp[i] 「另起炉灶」，此时单独的一个 nums[i] 的值，就是 dp[i]。

• dp[0] 根据定义，只有 1 个数，一定以 nums[0] 结尾，因此 dp[0] = nums[0]。

• 这里状态的定义不是题目中的问题的定义，不能直接将最后一个状态返回回去；

状态转移方程：

或者是

例六. leetcode63 不同路径II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

class Solution {
    public int uniquePathsWithObstacles(int[][] obs) {
        int col = obs.length;
        int row = obs[0].length;
        int[][] dp = new int[col+1][row+1];
        for(int i = 0; i < col; i++){
            if(obs[i][0] == 1){
                break;
            }
            else{
                dp[i][0] = 1;
            }
        }
        for(int i = 0; i < row; i++){
            if(obs[0][i] == 1){
                break;
            }
            else{
                dp[0][i] = 1;
            }
        }
        for(int i = 1; i < col; i++){
            for(int j = 1; j < row; j++){
                if(obs[i][j] == 1){
                    dp[i][j] = 0;
                }
                else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[col-1][row-1];
    }
}

本题目小结：（1）基本思想和例四一样，要注意的是处理石头那边

                     （2）遇见石头dp[i][j]就是0，但是，第一行第一列注意，一旦遇见石头后面都是0

例七. 474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

 
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] cnt = new int[len][2];
        for(int i = 0; i < len; i++){
            String temp = strs[i];
            int num0 = 0;
            int num1 = 0;
            for(int j = 0; j < temp.length(); j++){
                if(temp.charAt(j) == '0'){
                    num0++;
                }
                else{
                    num1++;
                }
            }
            cnt[i][0] = num0;
            cnt[i][1] = num1;
        }
        int[][] dp = new int[m+1][n+1];
        for(int k = 0; k < len; k++){
            for(int i = m; i >= cnt[k][0]; i--){
                for(int j = n; j >= cnt[k][1]; j--){
                    dp[i][j] = Math.max(dp[i][j],dp[i-cnt[k][0]][j-cnt[k][1]]+1);
                }
            }
        }
        return dp[m][n];
    }
}

本题目小结：（1）待写

                     （2）待写

 

例八. leetcode494 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i : nums) sum += i;
        int len = nums.length;
 
        int capacity = target > 0 ? sum-target : sum + target;
        if(capacity < 0 ||capacity % 2 != 0) return 0;
        capacity /= 2;
 
        int[] dp = new int[capacity+1];
        dp[0] = 1;
 
        for(int i = 0; i < len; i++){
            for(int j = capacity; j >= nums[i]; j--){
                dp[j] = dp[j] + dp[j-nums[i]];
            }
        }
        return dp[capacity];
    }
}

本题目小结：（1）待写

                     （2）待写

 

参考来源：【1】leetcode liweiwei1419 经典动态规划问题（理解「无后效性」）