【面试必刷101】动态规划1

摘要

【面试必刷101】系列blog目的在于总结面试必刷101中有意思、可能在面试中会被考到的习题。总结通用性的解题方法，针对特殊的习题总结思路。既是写给自己复习使用，也希望与大家交流。

【面试必刷101】递归/回溯算法总结I
【面试必刷101】递归/回溯算法总结II
【面试必刷101】链表
【面试必刷101】二叉树
【面试必刷101】二分查找
【面试必刷101】栈和队列
【面试必刷101】哈希
【面试必刷101】双指针
【面试必刷101】贪心算法、模拟、字符串

1 基础概念

应用场景：求最值。动态规划是运筹学的最优化方法，动态规划核心是穷举。

思路：

• 找到状态：明确dp数组表示的含义
• 状态转移：用题目的逻辑理清楚状态之间是怎样变化的
• 编写代码：赋初值、边界、状态变化、输出。

此文章重在总结题型，特别是出现在面试必刷101中的题型，希望能够帮到大家。

也可以参看之前写的背包问题，对动态规划有个补充。

2 面试必刷习题

2.1 最长公共子序列

import java.util.*;


public class Solution {
    
    public String LCS (String s1, String s2) {
    
        // 是不连续的
        // dp[i][j]表示是s1位置i和s2位置j的最长子序列的值
        // dp[i][j] = dp[i - 1][j - 1] + 1 (s1[i] == s2[j])
        // dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) (s1[i] != s2[j])
        // 然后怎么回溯呢？dp[i][j] == dp[i - 1][j - 1] 那么s1[i]要添加进来
        // dp[i][j] == dp[i - 1][j] 不添加，但是要跳到这边来
        // dp[i][j] == dp[i][j - 1] 不添加，但是i和j要调过来
        char[] c1 = s1.toCharArray(), c2 = s2.toCharArray();
        int l1 = c1.length, l2 = c2.length;
        if (l1 == 0 || l2 == 0) return "-1";
        int[][] dp = new int[l1 + 1][l2 + 1];
        for (int i = 1; i <= l1; i++) {
    
            for (int j = 1; j <= l2; j++) {
    
                if (c1[i - 1] == c2[j - 1]) {
    
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
    
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        if (dp[l1][l2] == 0) return "-1";

        StringBuilder sb = new StringBuilder();
        int i = l1, j = l2;
        while (i > 0 && j > 0) {
    
            // 这里的判断为啥不应该是dp[i][j] = dp[i - 1][j - 1] + 1？可能出现满足条件时，是有左边和上面的元素造成的。
            if (c1[i - 1] == c2[j - 1]) {
    
                sb.append(c1[i - 1]);
                i--;
                j--;
            } else {
    
                if (dp[i][j - 1] > dp[i - 1][j]) {
    
                    j--;
                } else {
    
                    i--;
                }
            }
        }
        return sb.reverse().toString();
    }
}

2.2 最长公共子串

import java.util.*;

public class Solution {
    
    public String LCS (String str1, String str2) {
    
        // 最长公共子串
        // dp[i][j]表示考虑s1的i位置和s2的j位置时，最长的公共串的个数
        // dp[i][j] = dp[i - 1][j - 1] + 1 (s1[i] == s2[j])
        // dp[i][j] = 0 (s1[i]!= s2[j])
        char[] s1 = str1.toCharArray(), s2 = str2.toCharArray();
        int l1 = s1.length, l2 = s2.length;
        int[] dp = new int[l2 + 1];
        int max = 0, idx = -1;
        for (int i = 1; i <= l1; i++) {
    
            for (int j = l2; j > 0; j--) {
    
                if (s1[i - 1] == s2[j - 1]) {
    
                    dp[j] = dp[j - 1] + 1;
                } else {
    
                    dp[j] = 0;
                }
                if (dp[j] > max) {
    
                    max = dp[j];
                    idx = i;
                }
            }
        }
        return str1.substring(idx - max, idx);
    }
}

2.3 最长上升子序列

import java.util.*;

public class Solution {
    
    public int LIS (int[] arr) {
    
        // dp[i] 表示以i结尾的最长上升子序列个个数
        // dp[i] = dp[i - 1] + 1
        int n = arr.length, res = 0;
        if (n == 0) return res;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
    
            int t = 0;
            for (int j = 0; j < i; j++) {
    
                if (arr[i] > arr[j]) {
    
                    t = Math.max(t, dp[j]);
                }
            }
            dp[i] = t + 1;
            res = Math.max(dp[i], res);
        }
        //System.out.println(Arrays.toString(dp));
        return res;
    }
}

2.4 打家劫舍（一）

取还是不取？是个问题。
错误的做法是：dp[i] = dp[i - 2]+nums[i]，然后计算dp[i]的最大值。
为啥错了呢？因为dp[i]的定义为i位置之前最大的，既然是最大的，就可能存在两种情况，取数、不取数
这种隔一个取一个的都是如此，两种情况。

import java.util.*;

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

打家劫舍（二）

import java.util.*;

public class Solution {
    
    public int rob (int[] nums) {
    
        int n = nums.length;
        if (n == 1) return nums[0];
        // 偷第一家，不偷最后一家
        int[] dp = new int[n + 1];
        dp[1] = nums[0];
        for (int i = 2; i < n; i++) {
    
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        int max = dp[n - 1];
        // 偷最后一家，不偷第一家
        dp = new int[n + 1];
        dp[2] = nums[1];
        for (int i = 3; i < n + 1; i++) {
    
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }

        return Math.max(max, dp[n]);
    }
}

2.5 最长回文子串

中心扩展，很容易做

import java.util.*;


public class Solution {
    

    public int getLongestPalindrome (String A) {
    
        // 中心扩展
        char[] c = A.toCharArray();
        int n = c.length;
        int res = 0, cnt = 0, tmp = 0;
        // 单边扩展
        for (int i = 0; i < n; i++) {
    
            cnt = 1;
            tmp = 1;
            while (i - cnt > -1 && i + cnt < n) {
    
                if (c[i - cnt] == c[i + cnt]){
    
                    tmp += 2;
                    cnt++;
                } else {
    
                    break;
                }
            }
            res = Math.max(res, tmp);
        }
        // 双边扩展
        for (int i = 1; i < n; i++) {
    
            cnt = 1;
            if (c[i - 1] == c[i]) {
    
                tmp = 2;
                while (i - 1 - cnt > -1 && i + cnt < n) {
    
                    if (c[i - 1 - cnt] == c[i + cnt]) {
    
                        tmp += 2;
                        cnt++;
                    } else {
    
                        break;
                    }
                }
                res = Math.max(res, tmp);
            }
        }
        return res;
    }
}

动态规划做法

import java.util.*;


public class Solution {
    
    public int getLongestPalindrome (String A) {
    
        // dp[i][j] 表示从i到j是不是回文子串
        // dp[i][j] == true dp[i+1, j-1] && c[i] == c[j]
        char[] c = A.toCharArray();
        int n = c.length, res = 1;
        boolean[][] dp = new boolean[n][n];
        dp[n - 1][n - 1] = true;
        for (int i = n - 2; i >= 0; i--) {
    
            for (int j = i; j < n; j++) {
    
                if (c[i] == c[j]) {
    
                    if (j - i < 2) dp[i][j] = true;
                    else {
    
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j]) {
    
                    res = Math.max(res, j - i + 1);
                }
            }
        }
        return res;
    }
}

2.6 数字字符串转化为IP地址

回溯法：写了好几次都出错了。
int与char类型判断是否相等，居然不会报错。原理是：链接

import java.util.*;

public class Solution {
    
    ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> restoreIpAddresses (String s) {
    
        char[] c = s.toCharArray();
        dfs(c, new StringBuilder(), 0, 1);
        return res;
    }
    
    public void dfs (char[] arr, StringBuilder sb, int s, int cnt) {
    
        if (s == arr.length && cnt == 5) {
    
            sb.delete(sb.length() - 1, sb.length());
            res.add(sb.toString());
            return;
        }
        if (cnt >= 5 || s >= arr.length) return;
        for (int i = 1; i < 4; i++) {
    
            if (digital(arr, s, s + i)) {
    
                int t = sb.length();
                for (int j = s; j < s + i; j++) {
    
                    sb.append(arr[j]);
                }
                sb.append('.');
                dfs(arr, sb, s + i, cnt + 1);
                // 回溯法
                sb.delete(t, sb.length());
            }
        }
    }

    public boolean digital (char[] arr, int i, int j) {
    
        if (j > arr.length) return false;
        if (j - i == 1 && arr[i] == '0') return true;
        if (j - i > 1 && arr[i] == '0') return false;
        int res = 0;
        while (i < j) {
    
            res = (res * 10 + (arr[i] - '0'));
            i++;
        }
        return res < 256;
    }
}

2.7 买股票的最好时机（三）

这个状态转移有点难想。

import java.util.*;

public class Solution {
    
    public int maxProfit (int[] prices) {
    
        // 状态：dp[0][i] 表示没有进行买卖
        // dp[1][i] 买入第一支 最大收益
        // dp[2][i] 卖出第一支
        // dp[3][i] 买入第二支
        // dp[4][i] 卖出第二支
        // dp[i][0] : dp[i][0] = 0 到i天为止没有买过股票的收益 
        // dp[i][1] : dp[i][1] = Max(dp[i - 1][1], dp[i - 1][0] - prices[i]) 到i天为止买过一只股票还没卖出的收益 
        // dp[i][2] : dp[i][2] = Max(dp[i - 1][2], dp[i - 1][1] + prices[i]) 到i天为止买过一次也卖出过一次股票的收益 
        // dp[i][3] : dp[i][3] = Max(dp[i - 1][3], dp[i - 1][2] - prices[i]) 到i天为止买过且卖过一次之后再买了一个股票的收益 // dp[i][4] : dp[i][4] = Max(dp[i - 1][4], dp[i - 1][3] + prices[i]) 到i天为止买过两次同事卖出过两次股票的最大收益 
        // dp[i][4] : dp[i][4] = Max(dp[i - 1][4], dp[i - 1][3] + prices[i]) 到i天为止买过两次同事卖出过两次股票的最大收益 
        int n = prices.length, maxVal = 0;
        int[][] dp = new int[n][5];
        Arrays.fill(dp[0], -10000);
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
    
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);  
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);  
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);  
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);  
        }
        return Math.max(dp[n - 1][2], dp[n - 1][4]);
    }
}

2.8 正则表达式匹配

这个题还是有点难度的，特别是当匹配到*时候，存在两种情况：

• 认为号是前一个出现0次：f[i][j] |= f[i][j - 2]意思是不管这个号了，看str与pattern前面两个匹配与否就好了。
• 认为前一个出现了多次：如果str在i位置与pattern的j-1位置相同，表示就可以满足了。f[i][j] |= f[i - 1][j]就看str前一个与pattern的j位置是否匹配就好了。（这里有点难理解：str前一个满足，然后*能够满足i，此时才能推出i位置的结果）

 import java.util.*;    
 public class Solution {
        
     public boolean match (String str, String pattern) {
        
         // write code here 
         int n = str.length();    
       int m = pattern.length();    
        boolean[][] f = new boolean[n + 1][m + 1];    
    
       for (int i = 0; i <= n; i++) {
        
            for (int j = 0; j <= m; j++) {
        
                //分成空正则和非空正则两种 
                if (j == 0) {
        
                    f[i][j] = i == 0;    
                } else {
        
                    //非空正则分为两种情况 * 和 非* 
                    if (pattern.charAt(j - 1) != '*') {
        
                        if (i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')) {
        
                            f[i][j] = f[i - 1][j - 1];    
                        }    
                   } else {
        
                       //碰到 * 了，分为看和不看两种情况 
                        //不看 
                        if (j >= 2) {
        
                             f[i][j] |= f[i][j - 2];    
                        }    
                        //看 
                        if (i >= 1 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.')) {
        
                            f[i][j] |= f[i - 1][j];    
                        }    
                     }    
                }    
             }    
        }    
        return f[n][m];    
    }    
}    

2.9 最长括号

有点难度的地方在于，可以续上，笑哭。

import java.util.*;

public class Solution {
    
    public int longestValidParentheses (String s) {
    
        // dp[i] 表示以i结尾的最长
        int n = s.length();
        int[] dp = new int[n];
        int res = 0;
        for (int i = 1; i < n; i++) {
    
            if (s.charAt(i) == ')') {
    
                if (s.charAt(i - 1) == '(') {
    
                    dp[i] = (i > 1 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
    
                    dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

栈的做法居然看不太懂。

import java.util.*;  
  
public class Solution {
      
    public int longestValidParentheses (String s) {
      
        Deque<Integer> dq = new LinkedList<>();  
        int idx = 0, res = 0;  
        int e = -1;  
        while (idx < s.length()) {
      
            if (s.charAt(idx) == '(') {
      
                dq.add(idx);  
            } else {
      
                if (dq.isEmpty()) {
      
                    e = idx;  
                } else {
      
                    dq.pollLast();  
                    if (dq.isEmpty()) {
      
                        res = Math.max(res, idx - e);  
                    } else {
      
                        res = Math.max(res, idx - dq.peekLast());  
                    }  
                }  
            }  
            idx ++;  
        }  
        return res;  
    }  
}  

3 知识点总结

1、子串与子序列问题
公共子串问题：

dp[i][j] = dp[i - 1][j - 1] + 1  (s1[i] == s2[j])
dp[i][j] = 0 (s1[i]!= s2[j])

子序列问题：

dp[i][j] = dp[i - 1][j - 1] + 1 (s1[i] == s2[j])
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) (s1[i] != s2[j])

最长上升子序列：

dp[i] = dp[j] + 1   j < i && arr[j] < arr[i] 遍历

特点是啥嘞？一般都是定义为[i,j]位置满足条件的个数，区别在于不等于的时候咋办？子串要求连续、子序列不要求连续。因此状态转移不同。

2、n选1问题
如打家劫舍、跳楼梯：特点是n种方案选择一种，得到最优解。

dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])

很好理解：选最优。

3、两端扩展问题
如回文子串和最长括号问题。此类问题就是往两边走。
回文子串：特点是，双端扩展由中间的状态进行转移。

dp[i][j] = dp[i + 1][j - 1]  (c[i] == c[j] , j > i) 

最长括号问题：特点是不仅可以双端扩展，还可以续上。

dp[i] = (i > 1 ? dp[i - 2] : 0) + 2;

dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;

4、链式多状态转移
买股票的最好时机：特点是在允许的条件下有多重状态，有的状态前置条件是上一种状态。

dp[i][0] : dp[i][0] = 0 //到i天为止没有买过股票的收益 
dp[i][1] : dp[i][1] = Max(dp[i - 1][1], dp[i - 1][0] - prices[i]) //到i天为止买过一只股票还没卖出的收益 
dp[i][2] : dp[i][2] = Max(dp[i - 1][2], dp[i - 1][1] + prices[i]) //到i天为止买过一次也卖出过一次股票的收益 
dp[i][3] : dp[i][3] = Max(dp[i - 1][3], dp[i - 1][2] - prices[i]) //到i天为止买过且卖过一次之后再买了一个股票的收益 
dp[i][4] : dp[i][4] = Max(dp[i - 1][4], dp[i - 1][3] + prices[i]) //到i天为止买过两次同事卖出过两次股票的最大收益 

5、其他
主要是状态转移难以确定。具体一点就是要抓住状态的定义，然后理清逻辑。
如：正则表达式匹配等。

4 总结

任重道远，砥砺前行。