动态规划：
条件：1. 最优子结构 2. 重叠则问题
设计思路：类似于递归，但是f（n）依靠数组去保存，不考递归，而是直接读取。从0--》n，从最简单的情况开始计算，而不是像递归那样从n开始回溯
通用的几种思路抽象：
- 考虑oper的各种可能操作，然后联系memo[i]之前的结果，求出当前的memo[i]
- memo[i]代表进行了oper[i]操作后的结果，根据memo[0..i]再加工求得最后结果
- 对多种状态变量，可能需要用2维数组，一个代表[0..i]即范围，一个代表C约束（见0-1背包问题）
70 爬楼梯
思路：
一 循环（3个变量，斐波那契数列）
二 动态规划
三 递归（会超时）
动态规划解法：
class Solution {
public:
int climbStairs(int n) {
if(n==1)
return 1;
if(n==2)
return 2;
int memo[n+1]={0};
memo[1]=1;
memo[2]=2;
for(int i=3;i<=n;i++){
memo[i]=memo[i-1]+memo[i-2];
}
return memo[n];
}
};
代码解释：
- 先设计整体思路，找到f（n）和f（n-1）之间的关系
- 容易得知f（n）=f(n-1)+f(n-2)，这是因为oper(n)只有2种选择，要么走1步，要么走2步，走一步的话，有f(n-1)种走法可以造成这种情况，同理走2步的话有f(n-2)种走法可以造成这种情况，因此f(n)的走法为2种情况之和
经验：
1.动态规划的话初值建议直接返回，因为有时候动态规划中的初值与数组迭代中的不一样，再一个就是如果数组长度依赖于数据规模的话，可能会导致数组越界。
练习 120 64
343 整数拆分
思路：
- 首先考虑初值（即拆分后小于原始数字的部分）直接返回
- 设计整体思路，整体思路就是对收到的数从1开始拆分，一直尝试到 数/2（包含！重要，之前没有包含导致结果错误，之所以除2是为了避免重复考虑，提升性能），判断是原本的memo[i]大还是拆分后的memo[i]大。拆分后的memo[i]=拆分的数 * memo[剩下的部分]
class Solution {
public:
int integerBreak(int n) {
if(n==1)
return 1;
if(n==2)
return 1;
if(n==3)
return 2;
int memo[n+1]={0};
memo[1]=1;
memo[2]=2;
memo[3]=3;
for(int i=4;i<=n;i++){
int m=i/2;
for(int j=1;j<=m;j++){
memo[i]=max(memo[i],j*memo[i-j]);
}
}
return memo[n];
}
};
代码详解：
- 首先拆分后小于原数值的都直接返回正确结果（1、2、3）
- 之后的都是大于等于原始数值的，开始考虑拆分后能够得到的最大乘积。oper(n)={1,2,3,4,5,6,...,n-1}，但实际上只需要考虑oper(n)={1,2,...,n/2}即可，因为超过n/2的部分跟之前的是重复的（相当于把两部分掉头而已），oper是我们拆出的整数A，余下的部分B可以依靠memo来求得最大的乘积memo[B]（一定大于等于B），遍历取得最大值，即求得当前memo
练习 279 91 63
198 打家劫舍
思路：
- 从第一家开始偷，每次oper（i）的操作是要么偷，要么不偷，然后根据memo[i]之前的结果推导现在的memo[i]的结果。
class Solution {
public:
int rob(vector<int>& nums) {
int n=nums.size();
if(n==0)
return 0;
if(n==1)
return nums[0];
if(n==2)
return max(nums[0],nums[1]);
int memo[n]={0};//memo[i]代表偷盗[0..i]能得到的最大财产
memo[0]=nums[0];
memo[1]=max(nums[0],nums[1]);
for(int i=2;i<n;i++){
memo[i]=max(nums[i]+memo[i-2],memo[i-1]);
}
return memo[n-1];
}
};
代码解释：
- 每一家要么偷，要么不偷
- 根据规则可以知道，要是偷，那么上一家就一定不能偷，能偷盗的最大值memo[i-2]+oper[i]；要是不偷当前的第i家，上一家可以偷，能偷的最大值是memo[i-1],二者比较谁大，取最大值即当前所求
经验：
发现动态规划好像就是递归啊。。。
练习 213 337 309
0-1背包问题
n个物品，重量第i个物品重量w[i]，价值v[i]，一个容量为C的背包，问该背包最大可装入多少价值。
思路：
- 定义f(i,c)为用c的背包装[0..i]的物品，能装入的最大价值
- 先考虑可能的oper(i)，发现要么放背包，要么不放背包
- i物品放背包，最大价值为v[i]+f(i-1,c-w[i]);i物品不放入背包，最大价值为f(i-1,c)，二者取最大值。
代码（待补充）
代码思路解释：
- 动态规划法：初始化初值，oper+memo[i][c]
- 记忆化搜索： 初始化数组（缓存），递归时先查结果，有则返回；没有就递归求得结果，保存到缓存，然后返回结果
优化问题：
空间优化（只需要二行？）
时间优化？
反解问题：
如何根据结果反解出操作？
300 最长上升子序列
网友评论