动态规划
记忆化搜索
斐波那契数列
自上而下的解决问题
vector<int> memo;
int fib(int n){
if(n == 0)
return 0;
if(n == 1)
return 1;
if(memo[n] == -1){
//这里设定如果memo[n]所对应的fib()没有计算过则为-1
memo[n]= fib(n-1)+fib(n-2);
return memo[n];
}
}动态规划
自下而上的解决问题
int fib(int n){
vector<int> memo(n+1,-1);
memo[0] = 0;
memo[1] = 1;
if(int i =0;i<=n;i++)
memo[i] = memo[i-1]+memo[i-2];
//自下而上的计算方式自动避免了重叠子问题
return memo[n];
}例题70
以下代码，多次重叠，时间超时
class Solution{
private:
int calcWays(int n){
if(n == 0||n==1)
return 1;
return calcWays(n-1)+calcWays(n-2);
}
public:
int climbStairs(int n){
return calcWays(n);
}
};改进，记忆化搜索
class Solution{
private:
vector<int> memo;
int calcWays(int n){
if(n == 0||n==1)
return 1;
if(memo[n] == -1)
memo[n] = calcWays(n-1)+calcWays(n-2);
return memo[n];
}
public:
int climbStairs(int n){
memo = vector<int>(n+1,-1);
return calcWays(n);
}
};动态规划
class Solution{
public:
int climbStairs(int n){
vector<int> memo(n+1,-1);
memo[0] = 1;
memo[1] = 1;
//从索引2开始。自下而上动态规划。
for(int i = 2;i<=n;i++)
memo[i] = memo[i-1]+memo[i-2];
return memo[n];
}
};例题120
例题64
例题343
最优子结构
通过求子问题的最优解，可以获得原问题的最优解
class Solution{
private:
vector<int> memo;
int max3(int a,int b,int c){
return max(a,max(b,c));
}
//将n进行分割（至少分割两部分），可以获得的最大乘积
int breakInteger(int n){
if(n==1)
return 1;
if(memo[n]!= -1)
return memo[n];
int res = -1;
for(int i =1;i<=n-1;i++)
//i + (n-i) 分割至少为两部分
res = max3(res,i*(n-i),i* breakInteger(n-i));
//这里因为i * breakInteger(n-i)不包括i * (n-i),所以三者比较
memo[n] = res;
return res;
}
public:
int integerBreak(int n){
memo = vector<int>(n+1,-1);
return breakInteger(n);
}
};class Solution{
private:
int max3(int a,int b,int c){
return max(a,max(b,c));
}
public:
int integerBreak(int n){
assert(n>=2);
vector<int> memo(n+1,-1);
memo[1] = 1;
for(int i =2;i<=n;i++)
//求解memo[i]
for(int j = 1;j<=i-1;j++)
//将i进行分割 j+(i-j)
memo[i] = max3(memo[i],j* (i-j),j*memo[i-j]);
return memo[n];
}
};例题279
例题91
例题62
例题63
例题198 House robber
class Solution{
private:
//记忆化搜索
vector<int> memo;
int tryRob(vector<int> &nums,int index){
if(index>=nums.size())
return 0;
if(memo[index] != -1)
return memo[index];
int res = 0;
for(int i = index;i<nums.size();i++)
res = max(res,nums[i] + tryRob(nums,i+2));
memo[index] = res;
return res;
}
public:
int rob(vector<int> &nums){
memo = vector<int> (nums.size(),-1);
return tryRob(nums,0);
}
};class Solution{
public:
int rob(vector<int> &nums){
int n =nums.size();
if(n == 0)
return 0;
vector<int> memo (n,-1);
//memo[i]表示考虑抢劫nums[i..n-1]所能获得的最大收益
memo[n-1] = nums[n-1]
for(int i = n-2;i>=0;i--)
//memo[i]
for(int j = i;j<n;j++)
memo[i] = max(memo[i],nums[j] + (j+2<n ? memo[j+2] : 0));
return memo[0];
}
};例题213 House Robber II
例题337 House Robber III
例题309
背包问题
有一个背包，容量为C。现有n种不同的物品，编号为0…n-1,其中每一件物品重量为w(i),价值为v(i).使得不超过背包容量的基础上，总价值最大
暴力解法O((2^n) * n)
贪心算法？优先放入平均价值最高的物品？
F(n,C) 考虑将n个物品放进容量为C的背包，使得价值最大
F(i,C) = F(i-1,c) –> max
= v(i) + F(i-1,c-w(i))
F(i,c) = max(F(i-1,c),v(i) + F(i-1,c-w(i)))
class Knapsack01{
private:
vector<vector<int>> memo;
//用[0...index]的物品，填充容积为c的背包的最大价值
int bestValue(const vector<int> &w,const vector<int> &v,int index,int C){
if(index < 0 || c<= 0)
return 0;
if(memo[index][c] != -1)
return memo[index][c];
int res = bestValue(w,v,index-1,c); //res为不选择index的策略
if(c > = w[index])
res = max(res,v[index] + bestValue(w,v,index-1,c-w[index]));
//选择index的策略
memo[index][c] = res;
return res;
}
public:
int knapsack01(const vector<int> &w,const vector<int> &v,int C){
int n = w.size();
memo = vector<vector<int>>(n,vector<int>(C+1,-1))
return bestValue(w,v,n-1,C);
//设定约束条件
}
};动态规划
class Knapsack01{
public:
int knapsack01(const vector<int> &w,const vector<int> &v,int C){
assert(w.size() == v.size() );
int n = w.size();
if(n == 0 || C = 0)
return 0;
vector<vector<int>> memo (2,vector<int>(C+1,-1));
for(int j = 0;j< = C;j++)
//物品 的背包容量
memo[0][j] = (j> = w[0] ? v[0] : 0)；
for(int i =1;i<n;i++)
for(int j =0;j<=C;j++ ){
memo[i%2][j] = memo[(i-1)%2][j]; //第一种策略[i]物品不放入 跳到[i-1]物品
if(j >= w[i] ) //如果对于第[i]个物品来说 容量j >w[i]
//重点max中的第一个memo[i][j]为上一步赋值的memo[i-1][j]
memo[i%2][j] = max(memo[i%2][j],v[i] + memo[(i-1)%2][j-w[i]]);
}
return memo [(n-1)%2][C];
//设定约束条件
}
};优化
class Knapsack01{
public:
int knapsack01(const vector<int> &w,const vector<int> &v,int C){
assert(w.size() == v.size() );
int n = w.size();
if(n == 0 || C = 0)
return 0;
<vector<int> memo (C+1,-1));
for(int j = 0;j< = C;j++)
for(int j = C;j>=w[i];j-- ){
//当背包剩余容量j<w[i]时终止，否则依次放入物品，max选取最优策略
//放入当前物品或者跳过当前物品
memo[j] = max(memo[j],v[i] + memo[j-w[i]]);
}
return memo [C];
//设定约束条件
}
};例题416 Partition equal subset sum
class Knapsack01{
private:
//memo[i][c]表示使用索引[0....i]的这些元素，是否可以完全填充一个容量为c的背包
//-1表示未计算 0表示不能被填充 1表示可以填充
vector<vector<int>> memo;
// 使用nums[0..index]是否可以完全填充容量为sum的背包
bool tryPartition(const vector<int> nums,int index,int sum){
if(sum == 0)
return true;
if(sum < 0 || index < 0)
return false;
if(memo[index][sum] != -1)
return memo[index][sum] == 1;
memo[index][sum] = tryPartition(nums,index-1,sum) ||
tryPartition(nums,index-1,sum-nums[index]) ?1 :0;
return memo[index][sum] ==1;
}
public:
bool canPartition(vector<int> nums){
int sum = 0;
for(int i = 0;i<nums.size(),i++){
assert(nums[i] > 0);
sum += nums[i];
}
if(sum%2 != 0)
return false;
memo = vector<vector<int>> (nums.size(),vector<int>(sum/2 +1,-1));
return tryPartition(nums,nums.size()-1,sum/2 );
}
};动态规划 背包问题
class Solution{
public:
bool canPartition(vector<int> & nums){
int sum = 0;
for(int i = 0;i<nums.size();i++){
assert(nums[i] > 0);
sum += nums[i];
}
if(sum%2)
return false;
int n = nums.size();
int C = sum/2;
vector<bool> memo (C+1,false);
for(int i = 0;i<= C;i++)
memo[i] = (nums[0] == i);
for(int i =1;i<n;i++)
for(int j = C;j>=nums[i];j--)
memo[j] = memo[j] || memo[j-nums[i]];
return memo[C];
}
};例题322 Coin change
例题377 Combination Sum IV
例题474 Ones and zeroes
例题139 Word Break
例题494 target sum
例题300 最长上升子序列
class Solution{
public:
int lengthOfLIS(vector<int> & nums){
if(nums.size() == 0)
return 0;
vecotr<int> memo(nums.size(),1);
for(int i = 1; i < nums.size();i++)
for(int j = 0; j<i;j++)
if(nums[j] < nums [i])
memo[i] = max(memo[i],1+memo[j]);
// 将以i结尾的memo[i]的最大值都计算出来
int res = 1;
for(int i = 0,i<nums.size();i++)
res = max(res,memo[i]);
return res;
};例题376
