只求秋招笔试能过，所以本文更多是怎么使用模板来解动态规划题，能过就好，对时间和空间的考虑不会太多
动态规划通过组合子问题的解得到原问题的解。 适合动态规划解决的问题具有重叠子问题和最优子结构两大特征，通常使用空间换时间的办法。
重叠子问题
动态规划的子问题具有重叠的，即各个子问题中包含重复的更小的子问题。若使用暴力法进行穷举，求解这些相同子问题会查收大量的重复计算，效率抵下。动态规划在第一次求解某个子问题时，会将子问题的解保存至矩阵中，后续遇到子问题时，则直接通过查表获取解，保证每个独立子问题制备计算一次，从而降低算法的时间复杂度。
最优子结构
如果一个问题的最优解可以由其子问题的最优解组合构成，那么称此问题具有最优解结构。动态规划从基础问题的解开始，不断进行迭代组合、选择子问题的最优解，最终得到原问题的最优解。
//明确 base case
if (amount == 0) return 0;
if (amount < 0) return -1;
dp(param)=dp(param-1) + 1;
min(
//明确「状态」,将小问题的解转化为大问题的解
dp(param+1),
dp(param-1),
) + 1;
//一般对memo有查询和插入两个操作
//查询，查看备忘录memo有没有相关数据，有就不用做了直接return
if (memo[amount] != 0)
return memo[amount];
//插入将子问题最优解保存
memo[point1][point2] = min(
//明确「状态」,将小问题的解转化为大问题的解
dp(param+1),
dp(param-1),
) + 1;
按上面的套路走，最后的解法代码就会是如下的框架：
class Solution {
int[]memo;
public int change(param) {
memo = new int[len];
return dp(coins,amount);
}
int dp(param) {
//明确 base case
if (amount == 0) return 0;
if (amount < 0) return -1;
//查看备忘录memo有没有相关数据，有就不用做了直接return
if (memo[amount] != 0)
return memo[amount];
//没有就递归选取子问题的解，并将该值保存
return memo[point1][point2] = min(
//明确「状态」,将小问题的解转化为大问题的解
dp(param+1),
dp(param-1),
) + 1;
}
}
明确 base case ==> amount=0 输出 0, amount和coins不匹配 result = -1
明确「状态」(怎么将大问题变为小问题) > 要求amount11时的硬币个数，可以求amount = 11-1、11-2、11-5的硬币个数然后加一
这里通过递归调用进行分解。
明确「选择」(获得子问题的解) ==> 和当前存储的值进行比较，取最小的数值
coinChange(11) = Min(coinChange(11-1),coinChange(11-2),coinChange(11-5))+1
class Solution {
int[]memo;
public int coinChange(int[] coins, int amount) {
memo = new int[amount+1];
Arrays.fill(memo, -666);
dp(coins,amount);
return dp(coins,amount);
}
int dp(int[] coins, int amount) {
//明确 base case
if (amount == 0) return 0;
if (amount < 0) return -1;
if (memo[amount] != -666)
return memo[amount];
int res = Integer.MAX_VALUE;
for(int i=0;i<coins.length;i++){
//明确「状态」
int sub = dp(coins,amount-coins[i]);
if (sub == -1) continue;
//明确「选择」
res = Math.min(res, sub+1 );
}
//将子问题的解存储用于之后的子问题。
memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
return memo[amount];
}
}
题目比较难，看不出base case和memo数组怎么用，先从状态转移入手
求"horse"到"ros"的操作数，就是求 替换"horse"的最小操作数 +1 或者 删除"horse"的最小操作数+1 或者 增加"horse"的最小操作数+1
用point1代表str1的索引，用point2代表str2的索引,int trans(int point1,int point2)代表从point1开始的字符串变换到从point2开始的字符串要的最小操作数
替换"horse"–>“rorse”,“ros” ：trans(point1+1,point2+1),
删除"horse"–>“orse”,“ros”：trans(point1+1,point2),
增加"horse"–>“rhorse”,“ros” ：trans(point1,point2+1)
求"horse"到"ros"的最小操作数，就是求min( 替换"horse"的最小操作数 ，删除"horse"的最小操作数，增加"horse"的最小操作数 )+1
综合 转移和选择，可以写出：
min(
//替换 "rorse","ros"
trans(point1+1,point2+1),
//删除 "orse","ros"
trans(point1+1,point2),
//增加 "rhorse","ros"
trans(point1,point2+1)
) + 1;
然后考虑边界情况，得到三个base case
//base case
//str1太短,补全str2剩余部分的长度
if (point1==str1.length()){
return str2.length()-point2;
}
//str1太长,删除多余部分
if (point2==str2.length()){
return str1.length()-point1;
}
//str1和str2在当前位置相同
if (str1.charAt(point1)==str2.charAt(point2)){
return trans(point1+1,point2+1);
}else return min(
//替换 "rorse","ros"
trans(point1+1,point2+1),
//删除 "orse","ros"
trans(point1+1,point2),
//增加 "rhorse","ros"
trans(point1,point2+1)
) + 1;
public class QuickTest {
public static void main(String[] args) {
System.out.println(new Solution().minDistance("horse","ros"));
}
}
class Solution {
String str1;
String str2;
public int minDistance(String word1, String word2) {
str1 = word1; str2 = word2;
// 状态转移 "horse","ros"
// trans(i,j) = (min(trans(i+1,j+1) 【i+1,j+1代表由于操作所降低的操作空间】))+ 1【代表一次操作】
return trans(0,0);
}
int trans(int point1,int point2){
//base case
//str1太短,补全str2剩余部分的长度
if (point1==str1.length()){
return str2.length()-point2;
}
//str1太长,删除多余部分
if (point2==str2.length()){
return str1.length()-point1;
}
if (str1.charAt(point1)==str2.charAt(point2)){
return trans(point1+1,point2+1);
}else return min(
//替换 "rorse","ros"
trans(point1+1,point2+1),
//删除 "orse","ros"
trans(point1+1,point2),
//增加 "rhorse","ros"
trans(point1,point2+1)
) + 1;
}
int min(int x,int y,int z){
return Math.min(x,Math.min(y,z));
}
}
import java.util.Arrays;
public class QuickTest {
public static void main(String[] args) {
System.out.println(new Solution().minDistance("intention","execution"));
}
}
class Solution {
String str1;
String str2;
int [][] memo;
public int minDistance(String word1, String word2) {
str1 = word1; str2 = word2;
//设置备忘录
memo = new int[word1.length()+1][word2.length()+1];
// 状态转移 "horse","ros"
// trans(i,j) = (min(trans(i+1,j+1) 【i+1,j+1代表由于操作所降低的操作空间】))+ 1【代表一次操作】
return trans(0,0);
}
int trans(int point1,int point2){
//base case
//str1太短,补全str2剩余部分的长度
if (point1==str1.length()){
return str2.length()-point2;
}
//str1太长,删除多余部分
if (point2==str2.length()){
return str1.length()-point1;
}
//查询备忘录
if (memo[point1][point2]!=0){
return memo[point1][point2];
}
if (str1.charAt(point1)==str2.charAt(point2)){
return memo[point1][point2] = trans(point1+1,point2+1);
}else return memo[point1][point2] = min(
//替换 "rorse","ros"
trans(point1+1,point2+1),
//删除 "orse","ros"
trans(point1+1,point2),
//增加 "rhorse","ros"
trans(point1,point2+1)
) + 1;
}
int min(int x,int y,int z){
return Math.min(x,Math.min(y,z));
}
}
