动态规划

具体来说，动态规划的一般流程就是三步：暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法。

就思考流程来说，就分为一下几步：找到状态和选择 -> 明确 dp 数组/函数的定义 -> 寻找状态之间的关系。

动态规划三要素

1. 重叠子问题
   
2. 最优子结构
   
3. 状态转移方程
   

框架

1. 明确 base case：
   
2. 明确「状态」：dp函数的参数，dp数组的索引
   
3. 明确「选择」：求最值时的选择
   
4. 定义 dp 数组/函数的含义：
   

按上面的套路走，最后的结果就可以套这个框架：

# 初始化 base case

dp[0][0][...] = base

# 进行状态转移

for 状态1 in 状态1的所有取值：

   for 状态2 in 状态2的所有取值：

       for ...

           dp[状态1][状态2][...] = 求最值(选择1，选择2...)

确定base case就是dp[i]最基础的情况，初始化为至少的可能即可

状态是原问题和子问题中变化的数据，dp数组的参数一般为状态（dp数组的索引一般为状态）

选择是导致状态改变的原因，for循环遍历所有选择，比较出最值即可选出最优解

总结一下如何找到动态规划的状态转移关系：

1、明确 dp 数组所存数据的含义。这一步对于任何动态规划问题都很重要，如果不得当或者不够清晰，会阻碍之后的步骤。

2、根据 dp 数组的定义，运用数学归纳法的思想，假设 dp[0...i-1] 都已知，想办法求出 dp[i]，一旦这一步完成，整个题目基本就解决了。

但如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组。

0-1背包问题

给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

这个题目中的物品不可以分割，要么装进包里，要么不装，不能说切成两块装一半。这也许就是 0-1 背包这个名词的来历。

1. 明确 状态 和 选择

如何才能描述出一个背包问题？

1. 给出背包容量限制
   
2. 给出几个可选物品
   

状态是子问题相比原问题变化的数据，所有状态有两个，即【背包的容量】和【可选择的物品】

选择是对于每件物品，【装进背包】或【不装进背包】

明白了状态和选择，动态规划问题基本上就解决了，只要往这个框架套就完事儿了：

for状态1in状态1的所有取值：

   for状态2in状态2的所有取值：

       for ...

           dp[状态1][状态2][...] = 择优(选择1，选择2...)

2. 根据 状态 定义dp数组

几个状态就是几维数组

dp数组是描述问题局面的一个数组。即用dp数组把状态表示出来

首先看看刚才找到的「状态」，有两个，也就是说我们需要一个二维dp数组，一维表示可选择的物品，一维表示背包的容量。

dp[i][w]的定义如下：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]。

比如说，如果 dp[3][5] = 6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。

PS：为什么要这么定义？便于状态转移，或者说这就是套路，记下来就行了。

根据这个定义，我们想求的最终答案就是dp[N][W]。base case 就是dp[0][..] = dp[..][0] = 0，因为没有物品或者背包没有空间的时候，能装的最大价值就是 0。

细化上面的框架：

intdp[N+1][W+1]

dp[0][..] = 0

dp[..][0] = 0

foriin [1..N]:

   forwin [1..W]:

       dp[i][w] = max(

           把物品i装进背包,

           不把物品i装进背包

       )

returndp[N][W]

3. 根据 选择 求出状态转移方程

简单说就是，上面伪码中「把物品i装进背包」和「不把物品i装进背包」怎么用代码体现出来呢？

这一步要结合对dp数组的定义和我们的算法逻辑来分析：

先重申一下刚才我们的dp数组的定义：

dp[i][w]表示：对于前i个物品，当前背包的容量为w时，这种情况下可以装下的最大价值是dp[i][w]。

1. 如果你没有把这第i个物品装入背包，那么很显然，最大价值dp[i][w]应该等于dp[i-1][w]。你不装嘛，那就继承之前的结果。
   
2. 如果你把这第i个物品装入了背包，那么dp[i][w]应该等于dp[i-1][w-wt[i-1]] + val[i-1]。
   首先，由于i是从 1 开始的，但wt数组和val数组下标从0开始，所以对val和wt的取值是i-1。
   而dp[i-1][w-wt[i-1]]也很好理解：你如果想装第i个物品，你怎么计算这时候的最大价值？换句话说，在装第i个物品的前提下，背包能装的最大价值是多少？
   显然，你应该寻求剩余重量w-wt[i-1]限制下能装的最大价值，加上第i个物品的价值val[i-1]，这就是装第i个物品的前提下，背包可以装的最大价值。
   

综上就是两种选择，我们都已经分析完毕，也就是写出来了状态转移方程，可以进一步细化代码：

foriin [1..N]:

   forwin [1..W]:

       dp[i][w] = max(

           dp[i-1][w],#第i件物品不放进背包

           dp[i-1][w-wt[i-1]] +val[i-1]#第i件物品放进背包

       )

returndp[N][W]

4. 编写完整代码+处理边界

每一层循环是一种状态

三种状态那么就三层循环

intknapsack(intW, intN, vector<int>&wt, vector<int>&val) {

   // vector 全填入 0，base case 已初始化

   vector<vector<int>>dp(N+1, vector<int>(W+1, 0));

   for (inti=1; i<=N; i++) {

       for (intw=1; w<=W; w++) {

           if (w-wt[i-1] <0) {

               // 当前背包容量装不下，只能选择不装入背包

               dp[i][w] =dp[i-1][w];

           } else {

               // 装入或者不装入背包，择优

               dp[i][w] =max(dp[i-1][w-wt[i-1]] +val[i-1],

                              dp[i-1][w]);

           }

       }

   }

   returndp[N][W];

}

例题1

背包体积和质量有限，求在体积和质量的范围内所能装载的物品价值最大是多少？

输入格式:

第一行 两个数 体积最大值(<400)和质量最大值(<400)

第二行 一个数 食品总数N(<50)

第三行－第3+N行

每行三个数 体积(<400) 质量(<400) 所含卡路里(<500)

输出格式:

一个数 所能达到的最大卡路里(int范围内)

输入样例:

320 350

4

160 40 120

80 110 240

220 70 310

40 400 220

输出样例:

在这里给出相应的输出。例如：

550

状态和选择

描述问题

1. 背包体积
   
2. 背包质量
   
3. 可选的物品
   

状态即上述两个

选择是物品装或不装

根据 状态 定义dp数组

用dp数组来描述状态

dp[i][v][m]：对于前i个物品，当前背包体积为v，质量为m，这种情况下可以装的最大价值是dp[i][v][m]

base case 是dp[0][..][..]=dp[..][0][..]=dp[..][..][0]，即没有物品，背包体积或质量为0，能装的最大价值为0

根据 选择 定义状态转移方程

体积数组是varr，质量数组是marr，价值数组是value

选择1：第i个物品未装入背包，直接继承上个结果

dp[i][v][m]=dp[i-1][v][m]

选择2：第i个物品装入背包

dp[i][v][m]=dp[i-1][v-varr[i-1]][m-marr[i-1]]+value[i-1]

编写代码（注意边界判断）

#include <bits/stdc++.h>

usingnamespacestd;

//V背包体积，W背包重量，n是物品数

intV,W,n;

intv[100],w[100],value[100];//分别是物品的体积数组，重量数组，价值数组

intdp[51][401][401];//n,V,W

intmain(){

   cin>>V>>W>>n;

   for(inti=1;i<=n;i++)

       cin>>v[i]>>w[i]>>value[i];

   for(inti=1;i<=n;i++)//遍历物品

       for(intj=1;j<=V;j++)//背包体积

           for(intk=1;k<=W;k++){//背包重量

               if(j-v[i]<0||k-w[i]<0)

                   // 当前背包容量装不下，只能选择不装入背包

                   dp[i][j][k]=dp[i-1][j][k];

               else {

                   // 装入或者不装入背包，择优

                   dp[i][j][k]=max(

                   dp[i-1][j][k],//i物品没装进背包

                   dp[i-1][j-v[i]][k-w[i]]+value[i]

                   );

               }

           }

   cout<<dp[n][V][W];

   return0;

}

例题2

0-1背包问题是经典的动态规划问题，这个问题大多用这样的故事开场：一个小偷溜进了一家博物馆，博物馆里排列着N件珍稀古董，每件古董都有重量和价值，而小偷带来的背包有重量限制W。因此，小偷的目的就是要选择部分古董，使其总重量不超过W且总价值最大。这故事听上去就像小偷在逛超市一样能轻松自如地挑选，而真实的情况是小偷提心吊胆，尤其是每拿下一件古董，随时都有触动警报的危险，所以小偷想尽可能少带几件古董立马跑路，但他的职业“素养”又不允许他不把背包装满。你能帮他解决这个困境吗？

输入格式:

第一行中给出2个整数值N和W, 其中1<N≤100表示古董的数量，1<W≤2000表示背包的重量限制。 接下来N行数据，每行两个正整数。第i行（1≤i≤N)的整数vi和wi分别表示第i件古董的价值和重量。 vi和wi的值均不超过2000。

输出格式:

在一行中输出两个整数值，用空格分开。第一个整数表示装背包能获得的最大总价值，第二个整数表示在获得最大价值的条件下装入背包里的古董的最少数量。

输入样例:

6 6

1 1

2 2

3 3

4 4

5 5

6 6

输出样例:

在这里给出相应的输出。例如：

6 1

状态和选择

状态

• 物品个数
  
• 背包的重量
  

选择

• 物品是否装到背包
  

根据 状态 定义dp数组

dp[i][w]：对于前i个物品，背包重量为w，所能装的最大价值为dp[i][w]

根据 选择 定义状态转移方程

1. 装到背包：dp[i][w]=dp[i-1][w-warr[i]]+value[i]
   
2. 未装到背包：dp[i][w]=dp[i-1][w]
   

编写代码

错误

#include<bits/stdc++.h>

using namespace std;

int N,W;//物品个数，背包重量

int varr[105],warr[105];//物品价值和重量数组

int dp[105][2005];//物品数目和背包重量的dp数组

int main(){

   cin>>N>>W;

   for(int i=1;i<=N;i++)

       cin>>varr[i]>>warr[i];

   for(int i=1;i<=N;i++)

       for(int j=1;j<=W;j++){

           if(j>=warr[i]){//背包剩余重量大于等于当前物品重量

               dp[i][j]=max(dp[i-1][j],dp[i-1][j-warr[i]]+varr[i]);

           }

           else

               dp[i][j]=dp[i-1][j];

       }

   cout<<dp[N][W];

   return 0;

}

正确

#include<bits/stdc++.h>

int N, W, vi[2005], wi[2005], dpv[2005], dpn[2005];

//dpv是用来存放最大价值的滚动数组

//dpn是用来存放最小数目的滚动数组

int min(int a, int b) {

   return a>b?b:a;

}

int main(void)

{

   scanf("%d%d", &N, &W);

   memset(dpv, 0, sizeof(dpv));

   memset(dpn, 1, sizeof(dpn));//函数将每一个二进制位都置为1，效果等同于将数组中每个值置为无穷大(int所能表示的最大正数)

   dpn[0] = 0;//填满容量为0的背包需要的物品数目为0

   for(int i = 1; i <= N; ++i)

       scanf("%d%d", &vi[i], &wi[i]);

   for(int i = 1; i <= N; ++i) {

       for(int j = W; j >= 1; --j) {

           if(j >= wi[i]) { //能放下当前物品

               if(dpv[j-wi[i]]+vi[i] >= dpv[j]) { //决定是否拿取当前物品

                   dpv[j] = dpv[j-wi[i]] + vi[i];//状态更新

                   dpn[j] = min(dpn[j], dpn[j-wi[i]]+1);//状态更新

               }

           }

       }

   }

   printf("%d %d\n", dpv[W], dpn[W]);

   return 0;

}

最长递增子序列

c++

#include<iostream>

#include<vector>

using namespace std;

class Solution {

private:

public:

   int lengthOfLIS(vector<int>& nums) {

       //dp[i]以nums[i]结尾的最长递增子序列长度

       vector<int> dp(nums.size(),1);

       for (int i = 0; i < nums.size(); i++)

           

           for (int j = 0; j < i; j++)

               if (nums[i] > nums[j])

                   dp[i] = max(dp[i], dp[j] + 1);

       int res = 0;

       for (int i = 0; i < nums.size(); i++)

           res = max(res,dp[i]);

       return res;

   }

};

c

#include<stdio.h>

#include<malloc.h>

int lengthOfLIS(int* nums, int numsSize) {

//创建dp[]，dp[i]代表以nums[i]结尾的最长递增子序列的长度

int* dp = (int*)malloc(sizeof(int) * numsSize);

//确定base case，dp[i]至少为1

for (int i = 0; i < numsSize; i++)

dp[i] = 1;

//如何求dp[i]呢？由数学归纳法，假设前i-1个dp数组元素已知，求dp[i]

for (int i = 0; i < numsSize; i++) {

for (int j = 0; j < i; j++)

  if (nums[i] > nums[j])

  dp[i] = dp[j] + 1 > dp[i] ? dp[j] + 1 : dp[i];

}

//根据dp的定义，遍历一遍dp数组，即可得出答案

int res = 0;

for (int i = 0; i < numsSize; i++)

res = res > dp[i] ? res : dp[i];

return res;

}

二维数组的array[][]行数和列数

1. 二维数组的本质还是一维数组，可以理解为一维数组中存放的元素还是一维数组，且这些一维数组的长度不一定相等
   
2. 二维数组的长度（行数，一行为一个一维数组）为一维数组的个数，即行数array.length
   
3. 二维数组的宽度（列数）为第i行一维数组的长度，即array[i].length
   

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

递归（自顶向下）

class Solution {

private:

   int recursion (int n){

       if(n==1||n==2)

           return n;

       return recursion(n-1)+recursion(n-2);

   }

public:

   int climbStairs(int n) {

       //递归

       return recursion(n);

   }

};

上述代码提交后会超时，因为有大量重叠子问题，会导致有重复计算而超时

我们可以建立一个备忘录来解决（记忆化搜索，自上而下）

如果能自上而下的解决问题，那么一定可以自下而上的解决

记忆化搜索（自顶向下）

#include<vector>

class Solution {

private:

   vector<int> memo;

   int recursion(int n){

       if(n==1|n==2)

           return n;

       if(memo[n]==-1)

           memo[n]=recursion(n-1)+recursion(n-2);

       return memo[n];

   }

public:

   int climbStairs(int n) {

   //备忘录

   //memo范围是[0,n]

   memo=vector<int>(n+1,-1);

   return recursion(n);

   }

};

动态规划（自底向上）

#include<vector>

class Solution {

public:

   int climbStairs(int n) {

       vector<int> memo(n+2,-1);

       memo[1]=1;

       memo[2]=2;

       for(int i=3;i<=n;i++){

           memo[i]=memo[i-1]+memo[i-2];

       }

       // memo[0]=1;

       // memo[1]=1;

       // for(int i=2;i<=n;i++){

       //     memo[i]=memo[i-1]+memo[i-2];

       // }

       return memo[n];

   }

};

343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

递归（自顶向下）

暴力解法：回溯遍历将一个数分割的所有可能 O(2^n)指数级别

#include<iostream>

using namespace std;

class Solution {

private:

   int max3(int a,int b,int c) {

       return max(a, max(b, c));

   }

   //将n进行分割（至少分两部分），可以获得的最大乘积

   int breakInteger(int n) {

       if (n == 1)

           return 1;

       int MAX;

       //只看第一层

       for (int i = 1; i <= n - 1; i++)

           MAX=max3(MAX,i*breakInteger(n - i),i*(n-i));

       return MAX;

   }

public:

   int integerBreak(int n) {

       return breakInteger(n);

   }

};

提交代码显示超时，因为我们有大量的重叠子问题，可以建立一个vector<int>来记录已经计算过的值，避免重复计算

记忆化搜索（自顶向下）

#include<iostream>

#include<vector>

using namespace std;

class Solution {

private:

   vector<int> memo;

   int MAX;

   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];

       //只看第一层

       for (int i = 1; i <= n - 1; i++)

           MAX=max3(MAX,i*breakInteger(n - i),i*(n-i));//因为至少分割成两部分，那么遗漏了i*(n-i)

       memo[n] = MAX;

       return MAX;

   }

public:

   int integerBreak(int n) {

       //初始化备忘录，[0,n]都为-1

       memo=vector<int>(n+1,-1);

       return breakInteger(n);

   }

};

动态规划（自底向上）

O(n^2)

#include<iostream>

#include<vector>

using namespace std;

class Solution {

private:

   vector<int> memo;

   int MAX;

   int max3(int a,int b,int c) {

       return max(a, max(b, c));

   }

public:

   int integerBreak(int n) {

       //数组元素的含义：memo[i]，表示将数字i分割后（至少两部分）得到的最大乘积

       vector<int> memo(n + 1, -1);

       //初始值

       memo[1] = 1;

       //从底向上（从2开始，循环到n，因为我们要求memo[n]，所以必然要先求出其最优子结构）

       for (int i = 2; i <= n; i++)

           //求解memo[i]

           for (int j = 1; j <= i - 1; j++)

               memo[i] = max3(memo[i], j * memo[i - j], j * (i - j));

       return memo[n];

   }

};