Everybody's good at something.
天生我材必有用。
引言
动态规划应该算是算法里比较难以掌握的了,经常是知其然不知其所以然。也是初学者学习算法中的‘拦路虎’,今天本武松将现场直播教学--如何打‘虎’,不对,考虑到老虎乃国家保护动物,本着‘保护动物,人人有责’的原则,换个说法,能用图的就不用文字。
最后希望各位看官老爷看完本文之后,都能够有所收获,最起码能够做到动态规划入门。 本文主要分享了什么是动态规划,动态规划的几个经典案例。
前言
什么是动态规划?
先整点官话
动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
数学思想:分阶段求解决策问题
动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。 (ps: 记住关键字,后面分析代码时会用到)
别着急,听我慢慢道来。
动态规划总体思路在于解题的步骤,本文大部分代码的实现思想都是基于这个解题步骤,更加的便于理解。
解题步骤
- 建立模型
- 寻找约束条件
- 寻找边界值
- 判断是否满足最优性原理
- 推出大问题和小问题的递推公式
- 建立矩阵表并填写
- 计算
话不多说,所有源码均已上传至github:
最长公共子序列
题目
给定两个字符串,求解这两个字符串的最长公共子序列。
比如字符串s1:abcbdab;字符串s2:bdcaba
则这两个字符串的最长公共子序列是:dcba
最长公共子序列长度为4
解析
先构建二阶矩阵表,相当于一个二维数组,这里用dp[i][j]表示,即
d[i][j]表示s1中前i个字符与s2中前j个字符分别组成的两个前缀字符串的最长公共长度.
初始化边界条件,这里 s1长度 m,s2长度n
s1,s2表示占位符,便于边界条件的处理
dp[i][0] = 0; (0 < i < m)
dp[0][j] = 0; (0 < i < n)
注:在这里,我通过不断地对i和j这两个数字量进行不断地求解,直到最终得到答案。这个数字量称之为状态。
当出现不匹配情况的时候,则我们取和它相邻的两个点的最大值,即
dp[i][j] = max{dp[i][j-1],dp[i-1][j]}; (s1[i-1] != s2[j-1])
同理的,如果匹配,则在原来基础上加一。即:
dp[i][j] = dp[i-1][j-1] + 1; (s1[i] == s2[j])
ps: 常规 数组索引为0是用来当占位符,便于计算,这里看表可知,可以把s1的 a和s2的b作为边界
呢现在的二阶矩阵表构建完毕,转换成代码如下:
准备 (二维数组的打印)
private void print(int[][] dp) {
for (int[] ds : dp) {
System.out.println(Arrays.toString(ds));
}
}复制代码
方法
private int solution(String s1, String s2) {
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int[][] dp = new int[str1.length][str2.length];
for (int i = 0; i < str1.length; i++) {
if (str1[i] == str2[0]){
dp[i][0] = 1;
}else{
dp[i][0] = 0;
}
}
for (int j = 0; j < str2.length; j++) {
if (str2[j] == str1[0]){
dp[0][j] = 1;
}else{
dp[0][j] = 0;
}
}
for (int i = 1; i < str1.length; i++) {
for (int j = 1; j < str2.length; j++) {
if (str1[i] == str2[j]){
dp[i][j] = dp[i-1][j-1] +1;
}else{
dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
}
}
}
print(dp);
int length = 0;
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < str1.length; i++) {
for (int j = 0; j < str2.length; j++) {
if (dp[i][j] == length && stringBuilder.indexOf(String.valueOf(str1[i])) == -1) {
stringBuilder.append(str1[i]);
}
length = Math.max(length,dp[i][j]);
}
}
System.out.println(stringBuilder.reverse().toString());
return length;
}复制代码
前两个for循环构建边界条件,第三个for循环填充二维数组。其实在这里dp[i][j](i,j取max)就是我们要求得长度。第四个for循环,是根据所得进行回溯,获得子序列,这个子序列也就是他的最长公共子串。
测试代码
LongestCommonSequence longestCommonSubString = new LongestCommonSequence();
String s1 = "abcbdab";
String s2 = "bdcaba";
int res = longestCommonSubString.solution(s1,s2);
System.out.println(res);复制代码
测试结果
最长公共子串
题目
给定两个字符串,求解这两个字符串的最长公共子串。
比如字符串str1:abcbdab;字符串str2:bdcaba
则这两个字符串的最长公共子串是:ab 或者 bd
这里的二阶矩阵表大致思路和求最长公共子序列有点相似,但是注意:
因为最长公共子串要求必须在原串中是连续的,所以一但某处出现不匹配的情况,此处的值就重置为0。即:
dp[i][j] = 0; (str1[i] != str2[j])
完整公式
- dp[i][0] = 0; (0<=i<=m)
- dp[0][j] = 0; (0<=j<=n)
- dp[i][j] = dp[i-1][j-1] +1; (str1[i] == str2[j])
- dp[i][j] = 0; (str1[i] != str2[j])
完整二阶矩阵表
呢现在的二阶矩阵表构建完毕,转换成代码如下:
准备
最长公共子串结果拼接 (这里的str 传 str1或者str2任意一个即可)
private String resJoint(String str, int x, int y) {
StringBuilder stringBuilder = new StringBuilder();
while (x >= 0 && y >= 0) {
stringBuilder.append(str.charAt(y--));
--x;
}
return stringBuilder.reverse().toString();
}复制代码
二维数组打印
private void print(int[][] dp) {
for (int[] ds : dp) {
System.out.println(Arrays.toString(ds));
}
}复制代码
方法一
private String solution(String str1, String str2) {
int[][] dp = new int[str1.length()][str2.length()];
char[] str1Chars = str1.toCharArray();
char[] str2Chars = str2.toCharArray();
for (int i = 0; i < str1Chars.length; i++) {
if (str1Chars[i] == str2Chars[0]) {
dp[i][0] = 1;
} else {
dp[i][0] = 0;
}
}
for (int j = 0; j < str2Chars.length; j++) {
if (str2Chars[j] == str1Chars[0]) {
dp[0][j] = 1;
} else {
dp[0][j] = 0;
}
}
for (int i = 1; i < str1Chars.length; i++) {
for (int j = 1; j < str2Chars.length; j++) {
if (str1Chars[i] == str2Chars[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = 0;
}
}
}
print(dp);
int max = dp[0][0];
//--> j
int x = 0;
// --> i
int y = 0;
for (int i = 0; i < str1Chars.length; i++) {
for (int j = 0; j < str2Chars.length; j++) {
if (dp[i][j] > max) {
max = dp[i][j];
y = i;
x = j;
}
}
}
System.out.println(max + "," + x + "," + y);
return resJoint(str1, x, y);
}复制代码
这里只分析第四个for循环,根据结果,求二阶矩阵中的最大值,由表可知,最长公共子串不是唯一的。这里只需要求出任意一组即可。如果需要全部罗列,只需要将x,y当数组存储,然后根据索引就可以拿出所有的最长公共子串了。
方法二
其实二阶矩阵表我们可以找出规律,将其转换为求二阶矩阵的最大地址对角线问题
private String solution2(String str1, String str2) {
char[] str1Chars = str1.toCharArray();
char[] str2Chars = str2.toCharArray();
int x = 0;
int y = 0;
int index = 0;
int max = 0;
//列
int row = 0;
//行
int col = str2Chars.length - 1;
//计算矩阵中的每一条斜对角线上的值
while (row < str1Chars.length) {
int i = row;
int j = col;
while (i < str1Chars.length && j < str2Chars.length) {
if (str1Chars[i] == str2Chars[j]) {
if (++index > max) {
max = index;
x = j;
y = i;
}
} else {
index = 0;
}
i++;
j++;
}
if (col > 0) {
--col;
} else {
++row;
}
}
System.out.println(max + "," + x + "," + y);
return resJoint(str1, x, y);
}复制代码
测试代码
LongestCommonSubString longestCommonSubString = new LongestCommonSubString();
String s1 = "abcbdab";
String s2 = "bdcaba";
String res = longestCommonSubString.solution(s1, s2);
System.out.println("最长公共子串为:" + res);
String res2 = longestCommonSubString.solution2(s1, s2);
System.out.println("最长公共子串为:" + res2);
复制代码
测试结果
方法一
方法二
最长递增子序列
题目
最长递增子序列是指找到一个给定序列的最长子序列的长度,使得子序列中的所有元素单调递增。
例如:{ 3,5,7,1,2,8 } 的 LIS 是 { 3,5,7,8 },长度为 4。
解析
这个问题和前两个问题又不太一样,需要自己和自己比较。
当 {3}的时候 LIS {3},长度 1
当 {3,5}的时候 LIS {3,5},长度 2
当 {3,5,7}的时候 LIS {3,5,7},长度 3
当 {3,5,7,1}的时候 LIS {3,5,7},长度 3
...
这里我们可以把原问题分解成 子问题来解决。(文章开头提过)
先考虑边界情况. F(1) = 1; i = 1;
根据上面可总结出公式
i表示 当前数组的索引,j表示当前数组的子数组的索引
F[i] = max{1,F[j]+1} ( F[j]<F[i] && j<i)
公式总结出来了,根据公式将其转换成代码,具体实现如下:
private int solution(int[] nums){
//推公式
//F[i] = max{1,F[j]+1|aj<ai && j<i}
int[] F = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
F[i] = 1;
}
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if(nums[j] < nums[i] && F[i] < F[j] + 1) {
F[i] = F[j] + 1;
}
}
}
int max = 0;
for (int i = 0; i < nums.length; i++) {
if(F[i] > max) {
max = F[i];
}
System.out.println("F[" + i + "] = " + F[i]);
}
System.out.println();
return max;
}复制代码
第一个for循环初始化 公式数组,将其全部置为1.
第二个for循环根据所得的公式将数组填满
第三个for循环获取满足条件的索引及最大值
测试代码
int[] nums = { 3,5,7,1,2,8 };
int res = new LongestIncreasingSubSequence().solution(nums);
System.out.println(res);复制代码
测试结果
根据打印log可以看出,1 - 2 -3 -4是连贯的,这说明 其对应的索引就是该问题的LIS
即{3,5,7,8}
当然 最长递减子序列的实现也就很容易了。
最大子序列和
题目
例如 [-2,1,-3,4,-1,2,1,-5,4],
连续子数组 [4,-1,2,1] 的和最大,为 6。
解析
这道题的求解思路和求最长递增子序列。这里直接罗列出状态转移方程式了:
dp[0] = nums[i]; (i = 0)
dp[i] = dp[i-1]>=0 ? dp[i-1]+nums[i] : nums[i] (i > 1)
具体实现如下:
private int solution(int[] nums){
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
if(dp[i - 1] >= 0) {
dp[i] = dp[i - 1] + nums[i];
}else {
dp[i] = nums[i];
}
System.out.println("dp[" + i + "] = " + dp[i]);
}
int res = dp[0];
for (int i = 1; i < dp.length; i++) {
if(dp[i] > res) {
res = dp[i];
}
}
return res;
}复制代码
当然还有一种更简单的解法只需要一个for循环就可以解决了,我只需要假设一个理想最大子序列res,然后遍历数组,当遍历值是正的,说明是增益的,加上,然后每次取max就可以了。
private int solution2(int[] nums){
int res = nums[0];
int sum = 0;
for(int num: nums) {
if(sum > 0) {
sum += num;
} else {
sum = num;
}
res = Math.max(res, sum);
}
return res;
}复制代码
测试代码
int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
int res = new MaxSubsequenceSum().solution(nums);
System.out.println("最大子序列和为:" + res);复制代码
测试结果
根据输出的结果可以看到子问题的每一种情况
进阶--01背包
题目
01背包 问题可以说是再经典不过了。
假设有N件物品和一个容量为V的背包。第i件物品的体积是v[i],价值是p[i],将哪些物品装入背包可使价值总和最大?
例题
N = 4, V = 8
解析
每一种物品都有两种可能即放入背包或者不放入背包。
可以用dp[i][j]表示第i件物品放入容量为j的背包所得的最大价值,则状态转移方程可以推出。
边界条件
dp[i][0] = dp[0][j] = 0 (i > 0,j > 0)
当背包容量小于物品重量时 即j < v[i],则装不进去,保持原状即可
dp[i][j] = dp[i-1][j] (j < v[i])
当能装下的时候,则需要考虑装入之前是什么状态,肯定是v[i-1][j-v[i]],当前物品的价值是p[i]
dp[i][j] = max{dp[i-1][j], dp[i-1][j-v[i]]+p[i]} (j >= v[i])
初始化二阶矩阵
根据公式填表
则dp[4][8] = 10,也就是装入物品的最大价值,但是装进去的是哪一些呢,则需要进行回溯了。
dp(i,j)=dp(i-1,j) 说明没有选择第i 个商品,则回到dp(i-1,j);
dp(i,j)=dp(i-1,j-v(i))+p(i) 说明装了第i个商品,该商品是最优解组成的一部分,随后我们得回到装该商品之前,即回到dp(i-1,j-v(i));
一直遍历到i=0结束为止.
略low的表示一下
dp[4][8] != dp[3][8] 并且 dp[4][8] =dp[3][8 - 5] + 6 ===> d[3][3]
说明第四个商品选中;
dp[3][3] = dp[2][3] 第三个商品没有被选中;
dp[2][3]!=dp[1][3]并且 dp[2][3] = dp[1][4-4] + 4 ====> dp[1][0]
说明第二件商品被选中;
dp[1][0] == dp[0][0]
说明第一件商品没有被选中。
具体实现代码如下
private int solution(int[] v, int[] p, int c) {
int[][] dp = new int[v.length][c + 1];
for (int i = 1; i < v.length; i++) {
for (int j = 1; j < c + 1; j++) {
if (j < v[i]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + p[i]);
}
}
}
print(dp);
int[] items = new int[v.length];
situation(items, v, p, dp, v.length - 1, c);
System.out.println("回溯选中的物品:(1表示选中)");
System.out.println("体积:" + Arrays.toString(v));
System.out.println("价格:" + Arrays.toString(p));
System.out.println("选中:" + Arrays.toString(items));
return dp[v.length - 1][c];
}复制代码
回溯方法
private void situation(int[] items, int[] v, int[] p, int[][] dp, int i, int j) {
if (i > 0) {
if (dp[i][j] == dp[i - 1][j]) {
situation(items, v, p, dp, i - 1, j);
} else if (j - v[i] >= 0 && dp[i][j] == dp[i - 1][j - v[i]] + p[i]) {
items[i] = 1;
situation(items, v, p, dp, i - 1, j -v[i]);
}
}
}复制代码
打印数组 print (参考上面)
测试代码
// 0 占位
int[] v = {0, 2, 3, 4, 5};
int[] p = {0, 3, 4, 5, 6};
int c = 8;
BackPack01 backPack01 = new BackPack01();
int max = backPack01.solution(v, p, c);
System.out.println("当体积为" + c + "时,最大价值为" + max);复制代码
测试结果
end
您的点赞和关注是对我最大的支持,谢谢!