-
【面试必刷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(); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
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); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
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; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
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]; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
打家劫舍（二）
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]); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
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; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
动态规划做法
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; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
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; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
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]); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
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]; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
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; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
栈的做法居然看不太懂。
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; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
3 知识点总结
1、子串与子序列问题
公共子串问题：dp[i][j] = dp[i - 1][j - 1] + 1 (s1[i] == s2[j]) dp[i][j] = 0 (s1[i]!= s2[j])- 1
- 2
子序列问题：
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])- 1
- 2
最长上升子序列：
dp[i] = dp[j] + 1 j < i && arr[j] < arr[i] 遍历- 1
特点是啥嘞？一般都是定义为
[i,j]位置满足条件的个数，区别在于不等于的时候咋办？子串要求连续、子序列不要求连续。因此状态转移不同。2、n选1问题
如打家劫舍、跳楼梯：特点是n种方案选择一种，得到最优解。dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])- 1
很好理解：选最优。
3、两端扩展问题
如回文子串和最长括号问题。此类问题就是往两边走。
回文子串：特点是，双端扩展由中间的状态进行转移。dp[i][j] = dp[i + 1][j - 1] (c[i] == c[j] , j > i)- 1
最长括号问题：特点是不仅可以双端扩展，还可以续上。
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;- 1
- 2
- 3
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天为止买过两次同事卖出过两次股票的最大收益- 1
- 2
- 3
- 4
- 5
5、其他
主要是状态转移难以确定。具体一点就是要抓住状态的定义，然后理清逻辑。
如：正则表达式匹配等。4 总结
任重道远，砥砺前行。
-
相关阅读:
【油猴脚本】00006 案例 Tampermonkey油猴脚本自定义表格列名称，自定义表格表头，自定义表格的thead里的td
三星电视“上新”在即，将有哪些新杀器？
定时器相关方法
Android Jetpack系列（七）：Room（使用篇）
linux安装Dns
Nwafu-OJ-1503 Problem 6 2019阶段1考试 题目5
软考 - 09 预约挂号管理系统
opencv4.x安装成功后，Pycharm导入无函数提示（但是可以正常使用imread、imshow等函数）
poll API接口 - 访问方式（三）
星宿UI2.4资源付费变现小程序源码 支持流量主
- 原文地址：https://blog.csdn.net/weixin_41399650/article/details/125824951
