前言 动态规划模型从尝试暴力递归到傻缓存到动态规划
四种模型和体系班两种模型一共六种模型
0.1 从左往右模型
0.2 范围讨论模型范围尝试模型 （这种模型特别在乎讨论开头如何如何 结尾如何如何）
玩家博弈问题，玩家玩纸牌只能那左或者右
0.3 样本对应样本对应模型（特别在乎两个样本结尾如何如何 最长公共子序列）
0.4 业务限制模型
动态规划只是暴力尝试的一个缓存
一 背包问题
1.1 描述
给定两个长度都为N的数组weights和values，
weights[i]和values[i]分别代表 i号物品的重量和价值。
给定一个正数bag，表示一个载重bag的袋子，
你装的物品不能超过这个重量。
返回你能装下最多的价值是多少?
1.2 分析
到当前货物的时候有两种选择，要么选择当前货物，要么不选择当前货物
base 条件的判断分析
if (rest < 0) {
return -1;}
这里为什么不能取return 0，因为上由传下来的剩下的bags的重量要大于0上由的值才是有意义的；
递归改动态规划
第一步找确定的值
if (index == w.length) {
return 0;
}
第二步找动态的值喝确定值之间的关系，动态的值时如何根据静态值退出来的
int p1 = process(w, v, index + 1, rest);
int next = process(w, v, index + 1, rest - w[index]);
这辆动态函数都需要依赖他的一行，最后一行又是确定值
1.3 尝试递归代码
// 所有的货，重量和价值，都在w和v数组里
// 为了方便，其中没有负数
// bag背包容量，不能超过这个载重
// 返回：不超重的情况下，能够得到的最大价值
public static int maxValue(int[] w, int[] v, int bag) {
if (w == null || v == null || w.length != v.length || w.length == 0) {
return 0;
}
// 尝试函数！
return process(w, v, 0, bag);
}
// index 0~N
// rest 负~bag
public static int process(int[] w, int[] v, int index, int rest) {
if (rest < 0) {
return -1;
}
if (index == w.length) {
return 0;
}
//不选择当前的货物
int p1 = process(w, v, index + 1, rest);
int p2 = 0;
//要选择当前的货物
int next = process(w, v, index + 1, rest - w[index]);
if (next != -1) {
p2 = v[index] + next;
}
return Math.max(p1, p2);
}1.4 改动态规划
递归改动态规划
第一步找确定的值
第二步找动态的值喝确定值之间的关系，动态的值时如何根据静态值退出来的
改动态规划 看是否有重复的情况
下面的p（3，10）都会重复
1.5 动态规划代码
public static int dp(int[] w, int[] v, int bag) {
if (w == null || v == null || w.length != v.length || w.length == 0) {
return 0;
}
int N = w.length;
int[][] dp = new int[N + 1][bag + 1];
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= bag; rest++) {
int p1 = dp[index + 1][rest];
int p2 = 0;
int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];
if (next != -1) {
p2 = v[index] + next;
}
dp[index][rest] = Math.max(p1, p2);
}
}
return dp[0][bag];
}
public static void main(String[] args) {
int[] weights = { 3, 2, 4, 7, 3, 1, 7 };
int[] values = { 5, 6, 3, 19, 12, 4, 2 };
int bag = 15;
System.out.println(maxValue(weights, values, bag));
System.out.println(dp(weights, values, bag));
}
}
二 字符对应数字对应的转换
2.1 描述
规定1和A对应、2和B对应、3和C对应...26和Z对应
那么一个数字字符串比如"111”就可以转化为:
"AAA"、"KA"和"AK"
给定一个只有数字字符组成的字符串str，返回有多少种转化结果
2.2 分析
第一步 到最后一个位置的时候前面做的决定共同构成收获了一个有效的点数
第二步 当前位置是0的是说明前面的做的决定策略错了，0是无效的转化，0没有对应的i字符
第三步 i位置不为0的时候说明该位置可以单转然后轮到 i+1位置去转
第四步 i和i+1位置共同决定，注意越界
2.3 代码
2.3.1尝试递归
// str只含有数字字符0~9
// 返回多少种转化方案
public static int number(String str) {
if (str == null || str.length() == 0) {
return 0;
}
return process(str.toCharArray(), 0);
}
// str[0..i-1]转化无需过问
// str[i.....]去转化，返回有多少种转化方法
public static int process(char[] str, int i) {
if (i == str.length) {
return 1;
}
// i没到最后，说明有字符
if (str[i] == '0') { // 之前的决定有问题
return 0;
}
// str[i] != '0'
// 可能性一，i单转
int ways = process(str, i + 1);
if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) {
//可能性二 i和i+1组合成算一种
ways += process(str, i + 2);
}
return ways;
}2.3.2 递归改动态规划
1.找到base条件
2.根据base条件推出其他情况
为什么取的是dp[0] 是因为递归尝试是从0开始的，递归最终往上返回的0
// 从右往左的动态规划
// 就是上面方法的动态规划版本
// dp[i]表示：str[i...]有多少种转化方式
public static int dp1(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str = s.toCharArray();
int N = str.length;
int[] dp = new int[N + 1];
dp[N] = 1;
for (int i = N - 1; i >= 0; i--) {
if (str[i] != '0') {
int ways = dp[i + 1];
if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) {
ways += dp[i + 2];
}
dp[i] = ways;
}
}
return dp[0];
}三 给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文
3.1 描述
给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文
arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来
返回需要至少多少张贴纸可以完成这个任务。
例子：str= "babac"，arr = {"ba","c","abcd"}
ba + ba + c 3 abcd + abcd 2 abcd+ba 2
所以返回2 张贴纸
3.2 分析
就把每一张贴纸作为第一张，有几张贴纸我就给你试多少种情况，答案必在其中，因为肯定有一张贴纸作为了第一张，我就试每一个第一张是哈，我把所有可能第一张都试了，后续最少张数你告诉我，所有分支中最少的那就是我要的
为什么排序？为了命中率高一点，不排序也可以
3.3 代码
public class Code03_StickersToSpellWord {
public static int minStickers1(String[] stickers, String target) {
int ans = process1(stickers, target);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
// 所有贴纸stickers，每一种贴纸都有无穷张
// target
// 最少张数
public static int process1(String[] stickers, String target) {
if (target.length() == 0) {
return 0;
//这里第一步返回
}
int min = Integer.MAX_VALUE;
for (String first : stickers) {
//假如贴纸stickers里面有5个，将这五个都作为第一个去试减去之后看target里面还剩多少target需要拼接的
String rest = minus(target, first);
//假如第一轮target里面试完了还有target需要再去贴的话进行下一轮
if (rest.length() != target.length()) {
//进行第一次后的下轮贴纸尝试
//这里第一步返回到这里
min = Math.min(min, process1(stickers, rest));
}
}
//要将第一次的加进来，每次递归process1没有走到上面的判断都会走到这里返回1或者Integer.MAX_VALUE
return min + (min == Integer.MAX_VALUE ? 0 : 1);
}
public static String minus(String s1, String s2) {
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int[] count = new int[26];
for (char cha : str1) {
count[cha - 'a']++;
}
for (char cha : str2) {
count[cha - 'a']--;
}
StringBuilder builder = new StringBuilder();
for (int i = 0; i < 26; i++) {
if (count[i] > 0) {
for (int j = 0; j < count[i]; j++) {
builder.append((char) (i + 'a'));
}
}
}
return builder.toString();
}3.4 改进 高效做法 优化
四 列子 两个字符串的最长公共子序列 使用的模型的是 （样本对应模型）
4.1 描述
给定两个字符串str1和str2，
返回这两个字符串的最长公共子序列长度
比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”
最长公共子序列是“123456”，所以返回长度6
4.2 分析 样本对应模型的经验是从最后一个开始对应
样本对应模型，他往往讨论结尾该如何组织可能性（经验）
4.3 最长公共子序列改动态规划分析
4.4代码
public class Code04_LongestCommonSubsequence {
public static int longestCommonSubsequence1(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
return 0;
}
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
// 尝试
return process1(str1, str2, str1.length - 1, str2.length - 1);
}
// str1[0...i]和str2[0...j]，这个范围上最长公共子序列长度是多少？
// 可能性分类:
// a) 最长公共子序列，一定不以str1[i]字符结尾、也一定不以str2[j]字符结尾
// b) 最长公共子序列，可能以str1[i]字符结尾、但是一定不以str2[j]字符结尾
// c) 最长公共子序列，一定不以str1[i]字符结尾、但是可能以str2[j]字符结尾
// d) 最长公共子序列，必须以str1[i]字符结尾、也必须以str2[j]字符结尾
// 注意：a)、b)、c)、d)并不是完全互斥的，他们可能会有重叠的情况
// 但是可以肯定，答案不会超过这四种可能性的范围
// 那么我们分别来看一下，这几种可能性怎么调用后续的递归。
// a) 最长公共子序列，一定不以str1[i]字符结尾、也一定不以str2[j]字符结尾
// 如果是这种情况，那么有没有str1[i]和str2[j]就根本不重要了，因为这两个字符一定没用啊
// 所以砍掉这两个字符，最长公共子序列 = str1[0...i-1]与str2[0...j-1]的最长公共子序列长度(后续递归)
// b) 最长公共子序列，可能以str1[i]字符结尾、但是一定不以str2[j]字符结尾
// 如果是这种情况，那么我们可以确定str2[j]一定没有用，要砍掉；但是str1[i]可能有用，所以要保留
// 所以，最长公共子序列 = str1[0...i]与str2[0...j-1]的最长公共子序列长度(后续递归)
// c) 最长公共子序列，一定不以str1[i]字符结尾、但是可能以str2[j]字符结尾
// 跟上面分析过程类似，最长公共子序列 = str1[0...i-1]与str2[0...j]的最长公共子序列长度(后续递归)
// d) 最长公共子序列，必须以str1[i]字符结尾、也必须以str2[j]字符结尾
// 同时可以看到，可能性d)存在的条件，一定是在str1[i] == str2[j]的情况下，才成立的
// 所以，最长公共子序列总长度 = str1[0...i-1]与str2[0...j-1]的最长公共子序列长度(后续递归) + 1(共同的结尾)
// 综上，四种情况已经穷尽了所有可能性。四种情况中取最大即可
// 其中b)、c)一定参与最大值的比较，
// 当str1[i] == str2[j]时，a)一定比d)小，所以d)参与
// 当str1[i] != str2[j]时，d)压根不存在，所以a)参与
// 但是再次注意了！
// a)是：str1[0...i-1]与str2[0...j-1]的最长公共子序列长度
// b)是：str1[0...i]与str2[0...j-1]的最长公共子序列长度
// c)是：str1[0...i-1]与str2[0...j]的最长公共子序列长度
// a)中str1的范围 < b)中str1的范围，a)中str2的范围 == b)中str2的范围
// 所以a)不用求也知道，它比不过b)啊，因为有一个样本的范围比b)小啊！
// a)中str1的范围 == c)中str1的范围，a)中str2的范围 < c)中str2的范围
// 所以a)不用求也知道，它比不过c)啊，因为有一个样本的范围比c)小啊！
// 至此，可以知道，a)就是个垃圾，有它没它，都不影响最大值的决策
// 所以，当str1[i] == str2[j]时，b)、c)、d)中选出最大值
// 当str1[i] != str2[j]时，b)、c)中选出最大值
public static int process1(char[] str1, char[] str2, int i, int j) {
if (i == 0 && j == 0) {
// str1[0..0]和str2[0..0]，都只剩一个字符了
// 那如果字符相等，公共子序列长度就是1，不相等就是0
// 这显而易见
return str1[i] == str2[j] ? 1 : 0;
} else if (i == 0) {
// 这里的情况为：
// str1[0...0]和str2[0...j]，str1只剩1个字符了，但是str2不只一个字符
// 因为str1只剩一个字符了，所以str1[0...0]和str2[0...j]公共子序列最多长度为1
// 如果str1[0] == str2[j]，那么此时相等已经找到了！公共子序列长度就是1，也不可能更大了
// 如果str1[0] != str2[j]，只是此时不相等而已，
// 那么str2[0...j-1]上有没有字符等于str1[0]呢？不知道，所以递归继续找
if (str1[i] == str2[j]) {
return 1;
} else {
return process1(str1, str2, i, j - 1);
}
} else if (j == 0) {
// 和上面的else if同理
// str1[0...i]和str2[0...0]，str2只剩1个字符了，但是str1不只一个字符
// 因为str2只剩一个字符了，所以str1[0...i]和str2[0...0]公共子序列最多长度为1
// 如果str1[i] == str2[0]，那么此时相等已经找到了！公共子序列长度就是1，也不可能更大了
// 如果str1[i] != str2[0]，只是此时不相等而已，
// 那么str1[0...i-1]上有没有字符等于str2[0]呢？不知道，所以递归继续找
if (str1[i] == str2[j]) {
return 1;
} else {
return process1(str1, str2, i - 1, j);
}
} else { // i != 0 && j != 0
// 这里的情况为：
// str1[0...i]和str2[0...i]，str1和str2都不只一个字符
// 看函数开始之前的注释部分
// p1就是可能性c) 完全不考虑i 所以减去1，可能考虑j
int p1 = process1(str1, str2, i - 1, j);
// p2就是可能性b) 完全不考虑j 所以减去1，可能考虑i
int p2 = process1(str1, str2, i, j - 1);
// p3就是可能性d)，如果可能性d)存在，即str1[i] == str2[j]，那么p3就求出来，参与pk
// 如果可能性d)不存在，即str1[i] != str2[j]，那么让p3等于0，然后去参与pk，反正不影响
int p3 = str1[i] == str2[j] ? (1 + process1(str1, str2, i - 1, j - 1)) : 0;
return Math.max(p1, Math.max(p2, p3));
}
}
//转化动态规划
public static int longestCommonSubsequence2(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
return 0;
}
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int N = str1.length;
int M = str2.length;
int[][] dp = new int[N][M];
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
for (int j = 1; j < M; j++) {
dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
}
for (int i = 1; i < N; i++) {
dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
}
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
int p1 = dp[i - 1][j];
int p2 = dp[i][j - 1];
int p3 = str1[i] == str2[j] ? (1 + dp[i - 1][j - 1]) : 0;
dp[i][j] = Math.max(p1, Math.max(p2, p3));
}
}
return dp[N - 1][M - 1];
}
}
