动态规划专题,总结一下dp使用的特点

DP-easy系列题

  1. Climbing Stairs(走一步还是走二步,考虑可能性的话是不是大多是+?sol[i] = sol[i-1] + sol[i-2]
  2. Best Time to Buy and Sell Stock(股票问题,感觉都不算dp,在遍历的中找一个最小值,用max函数维护一个num[i]-min的值,maxprofit = Math.max(maxprofit,prices[i]-min);min = Math.min(min,prices[i]),一个max和一个min维护的dp形式)
  3. Maximum Subarray(最大子序列和,好题,考虑两点:如果新来的num[i]比之前的sum还要大,那新的sum系列直接从新的num开始,并且将之前的sum记录下来;sum = Math.max(sum+num, num);sum_array = Math.max(sum_array,sum);,两个max函数维护的dp形式,第一个是curr的sum变动,第二个是history的sum值变动)
  4. House Robber(抢劫房子,偷或者不偷,只能选一种,是不是大多是max?则考虑最近的两个情况,money[i] = Math.max(nums[i]+money[i-2],money[i-1])

    DP-middle系列题

  5. Jump Game(青蛙跳问题,感觉和easy不同的就是,这属性限制性dp,而不是发散性,限制性的dp需要最后的值符合某个要求;这道题实际做的时候使用了逆向思维,从尾巴找起,因为失败发生的情况无法是跳到了一个0的地方,然后无法继续前进,所以逆向找到0,让设置step长度为1,往回找,要是找不到一个能跨越step的num,就失败了)

  6. Unique Paths(棋盘可能性,属于+的问题,思路简单,赋予边界初始值,然后+就完事了,sum[i][j] = sum[i-1][j]+sum[i][j-1]

  7. Coin Change(符合目标的最少硬币数,硬币,用或者不用,用的话,在之前的dp中找到减去该硬币面值的数,然+1,与不用的时候比,这里是根据硬币的可能性多次对dp进行更新,最后找到,dp[i] = Math.min(dp[i-coin]+1,dp[i])

  8. Longest Increasing Subsequence(无序数组中最长上升散序列,维护一个尾巴最小的上升数组,新来的数如果比数组都大,那就加长数组的长度,否则就更新上升数组,有必要重新写一次)

    DP-hard系列题

    Maximum Product Subarray(TODO)

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    
    class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] maxdp = new int[n+1];
        int[] mindp = new int[n+1];
        int maxVal = Integer.MIN_VALUE;
        maxdp[0] = 1;
        mindp[0] = 1;
        for (int i = 1; i < n+1; i++) {
            maxdp[i] = Math.max(maxdp[i-1]*nums[i-1], Math.max(mindp[i-1]*nums[i-1], nums[i-1]));
            mindp[i] = Math.min(mindp[i-1]*nums[i-1], Math.min(maxdp[i-1]*nums[i-1], nums[i-1]));
            maxVal = Math.max(maxVal, maxdp[i]);
        }
        return maxVal;
    }
    }      

    这道题,由于要考虑到正负数的问题,故要设立两个dp数组,考虑状态转移方程,当新来了一个数,可能的情况有三种,第一这个数很大,直接替换了直接的数组;第二这个数是正数,与之前的相乘使得max更大;第三这个数是负数与之前保存的最小负数相乘一跃变成最大。考虑完之后,可以用两个dp数组,三个方程求出最大值,这道题由于只涉及i和i-1的关系,还可以简化。

    Decode Ways()

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    
    class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int pre = 1;
        int now = s.charAt(n-1) == '0' ? 0 : 1;
        int curr = now;
        for (int i = n-2; i >= 0; i--) {
            if (s.charAt(i) == '0'){
                curr = 0;
            }
            else{
                curr = Integer.parseInt(s.substring(i,i+2))<27 ? pre+now:now;
            }
            pre = now;
            now = curr;
        }
        return curr;
    }
    }

    可能性问题,转移方程一般是+,即找(i-2)+(i-1)的个数,从尾巴开始找起,以2为窗口进行搜索,遇到0则需要改变状态量重新搜索。其中pre表示i-2,now表示i-1,curr表示i,使用时不要忘记,后面需要进行更新。

    Best Time to Buy and Sell Stock with Cooldown(TODO)

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    
    class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int max = 0, n = prices.length;
        int cooldown = 0;
        int sell = 0;
        int diff = -prices[0];
        for (int i = 1; i < n; i++) {
            int temp = cooldown;
            cooldown = Math.max(temp,sell);
            sell = Math.max(sell,prices[i] + diff);
            diff = Math.max(diff, temp - prices[i]);
            max = Math.max(Math.max(max,sell),cooldown);
        }
        return max;
    }
    }

    原来的做法实在看不懂,之后再试其他的方法,并且理解。

    Perfect Squares()

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    
    class Solution {
       
        public int numSquares(int n) {
        int[] res = new int[n+1];
        res[0] = 0;
        for (int i = 1; i < n+1; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= Math.sqrt(i); j++) {
                min = Math.min(res[i-j*j]+1,min);
            }
            res[i] = min;
        }
        return res[n];
    }
    }

    本质还是硬币凑数问题,思路也是一样的,先用小额度的数字去填dp数组,然后慢慢的用较大的数组去填,最小化使用数字的个数,区别就是i-j*j了,变成了减去一个平方数。

    Word Break()

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    
    class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0) return false;
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        int longestLen = 0;
        for (String word : wordDict) {
            if (word.length() > longestLen) {
                longestLen = word.length();
            }
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= longestLen; j++) {
                if (i>=j && dp[i-j]==true && wordDict.contains(s.substring(i-j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
    }

    这道题反而不是很想一道dp的题,主要还是那个判断条件,从最后一个字母倒推的话,必须有一个个的dp点为true,直到第一个数字。

    Word Break II(TODO)

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    
    class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        return dfs(s, wordDict, new HashMap<Integer, List<String>>(),0);
    }
    public List<String> dfs(String s, List<String> dict, Map<Integer, List<String>> map, int start) {
        if (map.containsKey(start)) return map.get(start);//剪枝,较少不必要的寻找
        List<String> res = new ArrayList<>();
        if (start == s.length()) {
            res.add("");//??
            return res;//结束的return
        }
        for (String word : dict) {
            if (s.startsWith(word, start)) {
                List<String> sublist = dfs(s, dict, map, start + word.length());
                for (String n : sublist) {
                    res.add(word + (n.length() == 0 ? "" : " ") + n);
                }
    
            }
        }
        map.put(start, res);
        return res;//寻找过程的return
    }
    }

    不是很能理解,放到之后去去看吧。

    Burst Balloons()