[编程题]LeetCode上的DynamicProgramming(动态规划)类型的题目

继上次把backTracking的题目做了一下之后：backTracking ，我把LeetCode的动态规划的题目又做了一下，还有几道比较难的Medium的题和Hard的题没做出来，后面会继续更新和加详细解法解释~
Dynamic Programming链接：https://leetcode.com/tag/dynamic-programming/

---

难度-Easy

---

Climbing Stairs 爬楼梯

这是一道经典的DP入门题目。一共有n阶台阶，我们一次可以上一阶或者两阶，问一共有多少种上楼梯的方法。
我们上楼梯的最后一部，也就是到第n阶的那一步，可能是从

• n-1阶往上走一阶，那么到n-1阶的时候一共有climbStairs(n-1)种走法


• n-2阶往上走两阶，那么到n-1阶的时候一共有climbStairs(n-2)种走法

于是到第n阶的时候就是上面两种走法之和：climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)；

如果我们每次递归climbStairs()的时候都要重新计算一次climbStairs的结果，那么运行时间成指数增长。我们可以开辟一个内存来存放结果，这里我们用HashMap。

这也是动态规划的思想：中间的结果要缓存起来，以备后续使用。

public class Solution {
    int res;
    Map resMap = new HashMap<>();
    public int climbStairs(int n) {
        if(n <2){
            return 1;
        } else {
            if(resMap.containsKey(n)){
                return(resMap.get(n));
            }
            res = climbStairs(n-1) + climbStairs(n-2);
            resMap.put(n,res);
            return res;
        }
    }
}

---

House Robber

你是一个专业的小偷，现在有一排屋子的钱等着你去偷，但是你不能偷相邻屋子的钱。假设以一个数组代表一排屋子，数字的每个元素代表每个屋子里面的钱，问你最多能偷多少钱？

我们说动态规划的思想是：中间的结果要缓存起来，以备后续使用。
因为题目规定相邻的两个屋子不能偷，那么就会有的屋子偷和有的屋子不偷。我们定义两个变量来存储上一次的结果：

• notRob ：表示上一个屋子不偷的时候我们最多能偷多少钱


• rob：表示上一个屋子偷的时候我们最多能偷多少钱

public class Solution {
    public int rob(int[] nums) {
        int rob = 0; 
        int notRob = 0;
        for(int num: nums){
            int curRob = notRob + num; //假设现在这个屋子我们偷 curRob 
            notRob = Math.max(rob, notRob); //现在这个屋子我们不偷
            rob = curRob;
        }
        return Math.max(rob, notRob);
    }
}

---

Best Time to Buy and Sell Stock买卖股票问题

给你一个数组表示这支股票在哪一天的价格，数组的下标表示第几天，元素代表这一天的股票价格，问再某一天买入再在某一天卖出最多能挣多少钱？

实际上这道题可以转化为求最大子数组之和的问题:Maximum Subarray。在《算法导论》里面看过用分治法来求，不过比较麻烦，既然它放在了动态规划的tag下面，那就尝试着用动态规划的思想去解。

和Maximum Subarray不一样的是，这道题的买卖股票的值是负的话，那么就干脆不买，即结果为0，而最大子数组的和就算为负数也会输出出来。便参考了Discuss里面的讨论：Kadane’s Algorithm

将表示股票价格的数组转化为每一天的股票价格差数组arr，然后依次遍历这个数组，当遍历到变量arr[i]的时候
用两个变量来缓存结果：

• maxIndex 表示目前加上这个元素arr[i]的最大值。若加上这个元素arr[i]之后为负数，则maxIndex 变为0，就是说之前一次买进股票到arr[i]卖出股票，赚的钱为负数，那么干脆抛弃，下次从arr[i+1]开始买进股票


• maxTotal 表示整个遍历整个数组arr时的最大值，每次都拿maxTotal 和 遍历到目前arr[i]时的maxIndex 比较，并更新为其中的最大值。

最后 maxTotal 就是最大值。

public class Solution {
    public int maxProfit(int[] prices) {
        int maxTotal = 0;
        int maxIndex = 0;
        for(int i = 1; i             maxIndex = Math.max(0, maxIndex += prices[i] - prices[i-1]);
            maxTotal = Math.max(maxTotal, maxIndex);
        }
        return maxTotal;
    }
}

---

Range Sum Query - Immutable

给你一个数组和两个下标 i 和 j ，算出 i 到 j 的和，注意sumRange 的方法会调用很多次。

既然题目说sumRange会调用很多次，那么我们就不能在sumRange里面计算 i 到 j 的和。
利用动态规划的思想，用原来的数组存 0 到下标 i 的和。

public class NumArray {

    int[] sums;

    public NumArray(int[] nums) {
        sums = new int[nums.length + 1];
        for(int i = 0; i             sums[i + 1] = sums[i] + nums[i]; 
        }
    }

    public int sumRange(int i, int j) {
        return sums[j+1] - sums[i];
    }
}


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);

---

难度-Medium

---

Maximum Subarray

给你一个数组，求最大的子数组的和是多少。

这道题和买卖股票的思想是一样的，参考上面的过程就好。唯一的不一样的是最大子数组的和有可能是负数。

public class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int maxIndex = nums[0];
        int maxTotal = nums[0];
        for(int i = 1; i             maxIndex = Math.max(nums[i], maxIndex += nums[i]); //和股票那道题的不一样之处
            maxTotal = Math.max(maxIndex, maxTotal);
        }
        return Math.max(maxIndex, maxTotal);
    }
}

---

Wiggle Subsequence

求最长的扭动序列。注意，这道题可以删除数组里面的某些元素来达到扭动序列。

这道题我们用两个变量来存储中间的计算结果：

• up：上一次上升趋势的时候的最大扭动序列的长度


• down： 上一次下降趋势的时候的最大扭动序列的长度

从0开始遍历数组，当遍历到 i 的时候， i-1 到 i 的趋势有：

• 上升趋势：那么这时候 0 ~ i 序列的最大扭动序列的长度 = 上一次下降趋势的时候的最大扭动序列的长度 + 1


• 下降趋势：那么这时候 0 ~ i 序列的最大扭动序列的长度 = 上一次上升趋势的时候的最大扭动序列的长度 + 1


• 趋势不变：那么这时候 0 ~ i 序列的最大扭动序列的长度不变

于是最后的结果就是 up 和 down 之间的最大值。

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int up = 1;
        int down = 1;
        for(int i = 1; i             if((nums[i] - nums[i-1]) > 0) up = down + 1;
            if((nums[i] - nums[i-1]) <0) down = up + 1;
        }
        return Math.max(up, down);
    }
}

---

Unique Paths

给你一个二维数组，问从左上角走到右下角一共有多少种走法，只能往下走或者往右走。

思路：
我们用一个数组res[][]来存中间的缓存结果，res[i][j] 表示从左上角[0][0]走到[i][j]时一共有多少种走法。
由于只能往下走或者往右走，则

• res[i][j] = 上面的元素有多少种走法 + 左边的元素有多少种走法。

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

---

Unique Paths II

这道题是上面一道题的扩展，唯一不同的是给出的矩阵里面有障碍物，遇到障碍物则走不通了。只需加一些判断条件就好。

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid[0][0] == 1) return 0;
        int[][] res = new int[obstacleGrid.length][obstacleGrid[0].length];
        for(int i = 0; i             if(obstacleGrid[i][0] == 1) break;
            res[i][0] = 1;
        }
        for(int i = 0; i 0].length; i++){
            if(obstacleGrid[0][i] == 1) break;
            res[0][i] = 1;
        }
        for(int i = 1; i             for(int j = 1; j 0].length; j++){
                if(obstacleGrid[i][j] == 0){
                    res[i][j] = res[i-1][j] + res[i][j-1];
                }
            }
        }
        return res[obstacleGrid.length-1][obstacleGrid[0].length-1];
    }
}

---

Minimum Path Sum

给你一个二维数组，数组里面有全是正数的值，问从左上走到右下角（只能往下走或者往右走），问路径和最小的值是多少。

思路：动态规划就是存储之前的结果用作下一步计算嘛，我们就用数组的 grid[i][j] 存从 grid[0][0] 到 grid[i][j]的最小路径和。那么 grid[i][j] 怎么求，注意到只能往下走或者往右走，那么 grid[i][j] 就等于它上面的和它左边的两个元素中的最小值，再加上它自己本身：

• grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1])

public class Solution {
    public int minPathSum(int[][] grid) {
        for(int i = 1; i <grid.length; i++){
            grid[i][0] += grid[i-1][0];
        }
        for(int i = 1; i <grid[0].length; i++){
            grid[0][i] += grid[0][i-1];
        }
        for(int i = 1; i <grid.length; i++){
            for(int j = 1; j <grid[0].length; j++){
                grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}

---

Longest Increasing Subsequence

给你一个数组，求它的最长增长子序列（注意不是字串）

用一个dp数组存最长的增长子序列，依次遍历给定的数组，然后把数组的元素 num 和 dp 数组里面的元素比较，有一下的结果：

• num 比 dp 数组里面所有元素都大，便插入在所有元素的后面


• num 在 dp 数组所有元素的中间，那么看应该在哪个位置，把那个位置的元素替换为num

这里用到的 Arrays.binarySearch 是用二分法来查找数组里面的元素，若元素存在在数组里面，则返回元素的索引，若不存在，则假设此元素应该存在在索引值为pos的位置，会返回 -pos-1

最后返回 dp 数组里面元素的个数就是最长的子序列的长度。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for(int num: nums){
            int pos = Arrays.binarySearch(dp, 0, len, num); //返回的是-（position）-1
            if(pos <0) pos = -(pos+1);
            dp[pos] = num;
            if(pos == len) ++len;
        }
        return len;
    }
}

---

Range Sum Query 2D - Immutable

public class NumMatrix {
    int[][] sum;
    int line;
    int col;

    public NumMatrix(int[][] matrix) {
        if(matrix == null || matrix.length == 0 ) return;
        sum = matrix;
        line = matrix.length;
        col = matrix[0].length;
        for(int i = 1; i             sum[i][0] += sum[i-1][0];
        }
        for(int j = 1; j             sum[0][j] += sum[0][j-1];
        }
        for(int i = 1; i             for(int j = 1; j                 sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1 > row2 || col1 > col2) return 0;
        if(row1 == 0 && col1 == 0) return sum[row2][col2];
        else if(col1 == 0) return sum[row2][col2] - sum[row1-1][col2];
        else if(row1 == 0) return sum[row2][col2] - sum[row2][col1-1];
        else return sum[row2][col2] - sum[row1-1][col2] - sum[row2][col1-1] + sum[row1-1][col1-1];
    }
}


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);

---

Decode Ways

字母A-Z对应的数组解码为：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26

给你一串数字字符串，问一共可以解码出多少种对应的字母字符串。
如 “12” 可以解码为 “AB” (1 2) 或者 “L” (12) 两种。

思路：
我们依次遍历字符串s，遍历到第 i 个字符的时候，用两个变量记录：

• last：在遍历到第 i-2 个字符的时候有多少种解码方式


• now：在遍历到第 i-1 个字符的时候有多少种解码方式

public class Solution {
    public int numDecodings(String s) {
        if(s == null || "".equals(s)) return 0;
        int last = 1;
        int now = 1;
        if(s.charAt(0) == '0') return 0;
        char pre = s.charAt(0);
        for(int i = 1; i             if(s.charAt(i) == '0') {
                if(pre >= '1' && pre <= '2'){
                    int temp = now;
                    now = last;
                    last = temp;
                } else {
                    return 0;
                }
            } else if(pre == '1'){
                int temp = now;
                now += last;
                last = temp;
            } else if(pre == '2' && s.charAt(i) >= '1' && s.charAt(i) <= '6'){
                int temp = now;
                now += last;
                last = temp;
            } else {
                last = now;
            }
            pre = s.charAt(i);
        }
        return now;
    }
}

---

Unique Binary Search Trees

给你一个整数 n，问 1~n 这 n 个数可以组成多少种二叉搜索树。
如 n = 3，会有一下几种：

思路：
我们可以用自底向上的方法，用数组：

• num 存从 1~n 的每个数可以组成二叉搜索树的种数。

那么对于第i个数来说，我们可以从 1~i 中随便挑出一个数 j 来当做根节点，那么 1~j-1 就作为 j 的左子树，j+1 ~ i 就作为 j 的右子树，那么

• 1~j-1 的左子树，一共有 num[j-1] 种组成二叉搜索树的方法


• j+1 ~ i 的右子树，它组成二叉搜索树的的方法其实和 j+1-j ~ i-j （1~i-j）的方法是一样的。比如：1 2 3 4 和 4 5 6 7是一样的

public class Solution {
    public int numTrees(int n) {
        //1 2 3 4 和 4 5 6 7是一样的
        int[] num = new int[n + 1];
        num[0] = 1;
        num[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <=i; j++){
                num[i] += num[j-1]*num[i-j];
            }
        }
        return num[n];
    }
}

---

Best Time to Buy and Sell Stock with Cooldown

又是买卖股票的问题，和上面那道买卖股票问题不一样的是这里加了个Cooldown“休息”的状态：

1. 在你把股票卖了之后，你不能立刻在下一天买进股票。（例如Cooldown“休息一天”）


2. 同一时间内你不能操作多次交易。（例如你必须卖了股票之后才能再买入）

例如：

股票为：[1, 2, 3, 0, 2]
最大利润：3
交易状态：[buy, sell, cooldown, buy, sell]

思路：
既然这里有3个状态，我们可以用状态机来解决。假设有s0,s1,s2三个状态，如下图所示：

• s0代表cooldown的状态，它可以由上一次是cooldown的状态继续cooldown转化而来，也可以由上一次是卖出股票后cooldown而来。


• s1代表买进股票之后的状态，他可以由上一次是cooldown然后买进股票而来，也可以是已经买进股票了，继续持有股票而来。


• s2代表卖出股票的状态，他只能由上一次是s1的状态卖出股票而来。

所以求最大的；利润，就是求每个状态的最大值;

• s0[i] = max(s0[i - 1], s2[i - 1])


• s1[i] = max(s1[i - 1], s0[i - 1] - prices[i])


• s2[i] = s1[i - 1] + prices[i]

最大的利润就是最后状态为刚卖出去股票“s2”和最后状态为cooldown“s0”两者的最大值。

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0) return 0;
        int[] s0 = new int[prices.length+1];
        int[] s1 = new int[prices.length+1];
        int[] s2 = new int[prices.length+1];
        s0[0] = 0;
        s1[0] = -(prices[0]);
        s2[0] = Integer.MIN_VALUE;
        int index = 1;
        for(int price: prices){
            s0[index] = Math.max(s0[index-1], s2[index-1]);
            s1[index] = Math.max(s1[index-1], s0[index-1] - price);
            s2[index] = s1[index-1] + price;
            index++;
        }
        return Math.max(s2[prices.length], s0[prices.length]);
    }
}

---

Combination Sum IV

给你一个全是正数且不重复的数组和一个数字target，问利用数组里面的数字有多少种方式组合，使得加起来的和等于target。

例如：

nums = [1, 2, 3]
target = 4

可能的组合为：

(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

这道题我一开始是用backTracking的套路来写的，得出来的结果是对的，但是提交的时候超时了，于是就想到要用DP来做，下面是backTracking的代码：

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        if(target == 0 || nums == null || nums.length == 0) return 0;
        List> res = new ArrayList<>();
        Arrays.sort(nums);
        backTracking(res, new ArrayList<>(), nums, target);
        return res.size();
    }

    private void backTracking(List> res, List list, int[] nums, int target){
        if(target <0) return;
        if(target == 0) res.add(new ArrayList<>(list));
        else {
            for(int i = 0; i                 list.add(nums[i]);
                backTracking(res, list, nums, target - nums[i]);
                list.remove(list.size()-1);
            }
        }
    }
}

下面是动态规划DP的代码:

思路：我们用自底向上的方法，用res数组来存中间的缓存结果，res[i] 表示 有多少种组合方式的和等于i，那么对于i+1来说，遍历nums数组，对于每一个元素num，如果num > i+1，那么num是无论如何组合都不会和等于i+1，如果不是：

• 恰好 num == i+1，即由加一种组合方式，就只是num本身，那么在原来的基础上res[i+1]加1即可


• num
  

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        if(target == 0 || nums == null || nums.length == 0) return 0;
        int[] res = new int[target+1];
        Arrays.sort(nums);
        for(int i = 1; i             for(int num: nums){
                if(num > i) break;
                else if(i == num) res[i] += 1;
                else {
                    res[i] += res[i-num];
                }
            }
        }
        return res[target];
    }
}

---

Perfect Squares

给定一个正整数n，让我们找出最少的平方数使得他们加起来等于n。（平方数就是由某个数的平方得来的）

例如：

n = 12

返回 3，因为

12 = 4 + 4 + 4

思路：
动态规划的思想就是缓存之间的结果。我们用自底向上的方法，用res数组存1到n的结果。res[i]表示最少的平方数使得他们加起来等于i。

public class Solution {
    public int numSquares(int n) {
        int[] res = new int[n+1];
        Arrays.fill(res, Integer.MAX_VALUE);
        res[0] = 0;
        for(int i = 1; i             int min = Integer.MAX_VALUE;
            int j = 1;
            while(i >= j*j){
                min = Math.min(min, res[i-j*j] + 1);
                ++j;
            }
            res[i] = min;
        }
        return res[n];
    }
}

---

Count Numbers with Unique Digits

public class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if(n == 0) return 1;
        int res = 10;
        int base = 9;
        for(int i = 2; i <= n && i <=10; ++i){
            base = base * (9 + 2 - i);
            res += base;
        }
        return res;
    }
}

---

Coin Change换零钱

给定一个数组coins代表有零钱的面额，问找开amount这个数的钱用的最少零钱的张数是多少？找不开则返回-1

例如：

coins = [1, 2, 5], amount = 11

返回：

3 因为(11 = 5 + 5 + 1)

思路：
用一个res 数组缓存中间结果，用自底向上的方法，res[i]表示找开i的最少零钱数。res[i]先初始化为Integer.MAX_VALUE，表示找不开i。

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins == null || coins.length == 0) return -1;
        if(amount == 0) return 0;
        int[] res = new int[amount + 1];
        for(int i = 1; i             res[i] = Integer.MAX_VALUE;
        }
        Arrays.sort(coins);
        for(int i = 1; i             for(int j = 0; j                 if(i continue;
                if(i >= coins[j]){
                    int tag = res[i - coins[j]];
                    if(tag != Integer.MAX_VALUE){ //如果找的开
                        res[i] = Math.min(tag + 1, res[i]);
                    }
                }
            }
        }
        return res[amount] == Integer.MAX_VALUE? -1: res[amount];
    }
}

---

Palindrome Partitioning II

给定一个字符串s，返回最少的分割次数使得字串全是回文。

思想：

• 矩阵dp[i][j] 存的是给定的字符串 s 的 s[i~j] 字串是否是回文


• 数组res[i] 存的是 s[i~n-1] 的最小分割次数

然后如果 dp[i][j] == true 的话

• 如果 j == n-1 说明 s[i~n-1] 是回文，则不用分割，即分割次数为0，res[i] = 0；


• 如果 j！= n-1 说明 对s[i~n-1]，在 j 这里切一刀，s[i~j] 是回文，看 s[j+1…n-1]的最小切割数（res[j+1]）是多少，res[j+1] + 1 和 原来的 res[i] 比较，取最小值。


• 即 res[i] = Math.min(res[i], res[j+1]+1)

res[0] 就是答案。

public class Solution {
    public int minCut(String s) {
        if(s == null || s.length() <2) return 0;
        int length = s.length();
        boolean[][] dp = new boolean[length][length];
        int[] res = new int[length];
        for(int i = 0; i <length; i++){
            Arrays.fill(dp[i], false);
        }
        for(int i = length-1; i >= 0; i--){
            res[i] = length - i - 1; //worse
            for(int j = i; j <length; j++){
                /*如果字符串的两边相等的情况下 1、这个字符串只有两个字符 2、这个字符串不止两个字符，但是除了这两个字符的中间字符串是回文 那么这个字符串就是回文 */
                if(s.charAt(i) == s.charAt(j) && (j-i <2 || dp[i+1][j-1])){
                    dp[i][j] = true;
                    if(j == length-1){
                        res[i] = 0;
                    } else {
                        res[i] = Math.min(res[i], res[j+1]+1);
                    }
                }
            }
        }
        return res[0];
    }
}

---

Counting Bits

给定一个正整数num，对于 0 ≤ i ≤ num 的每一个 i ，计算它的二进制表示中有多少个1，结果作为一个数组返回。

思路：
总不能每个都转化为二进制，再来数里面有多少个1吧，这是最笨的方法。那么我们再想远一点。
我们可以在纸上画一下各个数字的二进制表示：

0 0
1 01
2 10
3 11
4 100
5 101
6 110
7 111
8 1000
9 1001

可以看出：

• 数字1和2是在数字0的二进制后面分别拼接上1和0而形成的


• 数字2和3是在数字1的二进制后面分别拼接上1和0而形成的


• ···


• 数字n-1和n是在数字n/2的二进制后面分别拼接上1和0而形成的

所以数字n的二进制有多少个1等于数字n/2的二进制有多少个1加上n的末尾是不是1：

res[i] = res[i / 2] + i % 2.

public class Solution {
    public int[] countBits(int num) {
        int[] res = new int[num+1];
        if(num <0) return res;
        for(int i = 0; i             res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}