目录
例题引入---找到解决问题模版
画图分析:
使用动态规划解决(第二问与第一问的不同之处用绿色来标记)
1.状态表示
dp[i][j]表示从前i个物品中挑选，总体积不超过j的所有选法中，所挑选出来的最大价值
dp[i][j]表示从前i个物品中挑选，总体积等于j的所有选法中，所挑选出来的最大价值
2.状态转移方程
3.初始化 根据01背包问题得知，我们只需初始化第一行即可
4.填表顺序 从上往下填每一行，每一行从左往右
5.返回值 对于第一问的是直接返回dp[n][V]
第二问则是需要判断下dp[n][V]==-1?0:dp[n][V]
具体代码 ---优化前
#include <iostream>
#include <string.h>
using namespace std;
const int N=1010;
int n,V;
int w[N],v[N],dp[N][N];
int main()
{
//读入数据
cin>>n>>V;
for(int i=1;i<=n;++i)
cin>>v[i]>>w[i];
//解决第一问
for(int i=1;i<=n;++i)
for(int j=0;j<=V;++j)
{
dp[i][j]=dp[i-1][j];
if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
}
cout<<dp[n][V]<<endl;
//解决第二问
memset(dp,0,sizeof dp);
for(int j=1;j<=V;++j) dp[0][j]=-1;
for(int i=1;i<=n;++i)
for(int j=0;j<=V;++j)
{
dp[i][j]=dp[i-1][j];
if(j>=v[i] && dp[i][j-v[i]]!=-1)
dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
}
cout<<(dp[n][V]==-1? 0:dp[n][V]);
return 0;
}做优化
优化后的代码
#include <iostream>
#include <string.h>
using namespace std;
const int N=1010;
int n,V;
int w[N],v[N],dp[N];
int main()
{
//读入数据
cin>>n>>V;
for(int i=1;i<=n;++i)
cin>>v[i]>>w[i];
//解决第一问
for(int i=1;i<=n;++i)
for(int j=v[i];j<=V;++j)
{
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
cout<<dp[V]<<endl;
//解决第二问
memset(dp,0,sizeof dp);
for(int j=1;j<=V;++j) dp[j]=-1;
for(int i=1;i<=n;++i)
for(int j=v[i];j<=V;++j)
{
if(dp[j-v[i]]!=-1)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
cout<<(dp[V]==-1? 0:dp[V]);
return 0;
}LeetCode 经典OJ题
1.第一题
画图分析：
使用动态规划解决
1.状态表示
dp[i][j]表示从前i个硬币中挑选，总和正好等于j，所有的选法中，最少的硬币数
2.状态转移方程
3.初始化
4.填表顺序 从上往下每一行，每一行从左往右
5.返回值 dp[n][amount]>=INF? -1:dp[][amount]
具体代码
int coinChange(vector<int>& coins, int amount)
{
const const int INF=0x3f3f3f3f;
int n=coins.size();
vector<vector<int>> dp(n+1,vector<int>(amount+1));
for(int j=1;j<=amount;++j) dp[0][j]=INF;
for(int i=1;i<=n;++i)
for(int j=0;j<=amount;++j)
{
dp[i][j]=dp[i-1][j];
if(j>=coins[i-1]) dp[i][j]=min(dp[i][j],dp[i][j-coins[i-1]]+1);
}
return dp[n][amount]>=INF? -1:dp[n][amount];
}
//优化后
int coinChange(vector<int>& coins, int amount)
{
const const int INF=0x3f3f3f3f;
int n=coins.size();
vector<int>dp(amount+1,INF);
dp[0]=0;
for(int i=1;i<=n;++i)
for(int j=coins[i-1];j<=amount;++j)
dp[j]=min(dp[j],dp[j-coins[i-1]]+1);
return dp[amount]>=INF? -1:dp[amount];
}2.第二题
画图分析：
使用动态规划解决
1.状态表示
dp[i][j]表示从前i个硬币中挑选，总和正好等于j，一共有多少种选法
2.状态转移方程
3.初始化 初始化第一行，第一个位置前0个凑出0元，即什么都不选，是一种方法，初始化为1，其余位置是凑不出来的，即初始化为0
4.填表顺序 从上往下每一行，每一行从左往右
5.返回值 dp[n][amount]
具体代码
int change(int amount, vector<int>& coins)
{
vector<unsigned int> dp(amount + 1);
dp[0] = 1;
for(int i=1;i<=coins.size();++i)
for(int j = coins[i-1]; j <= amount; j++)
dp[j] += dp[j - coins[i-1]];
return dp[amount];
}3.第三题
画图分析：
对于本题可以从左往右进行挑选完全平方数，来合成数n,且每个完全平方数都能重复进行选择
这就是完全背包问题 使用动态规划解决
1.状态表示
dp[i][j]表示从前i个完全平方数中进行挑选，总和恰好为j,完全平方数的数量
2.状态转移方程
3.初始化 初始化第一行，第一个位置初始化为0，其余位置的状态是不存在的，因为题目求的是min,为不影响填表，初始化为一个较大值ox3f3f3f3f
4.填表顺序 从上往下，从左往右
5.返回值 dp[sqrt(n)][n]
具体代码：
int numSquares(int n)
{
int m=sqrt(n);
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int j=1;j<=n;++j) dp[0][j]=0x3f3f3f3f;
for(int i=1;i<=m;++i)
for(int j=0;j<=n;++j)
{
dp[i][j]=dp[i-1][j];
if(j>=i*i) dp[i][j]=min(dp[i][j],dp[i][j-i*i]+1);
}
return dp[m][n];
}
//优化后
int numSquares(int n)
{
int m=sqrt(n);
vector<int>dp(n+1,0x3f3f3f3f);
dp[0]=0;
for(int i=1;i<=m;++i)
for(int j=i*i;j<=n;++j)
{
dp[j]=min(dp[j],dp[j-i*i]+1);
}
return dp[n];
}其余的一些背包问题
1.二维费用的背包问题
二位费用的背包问题简单来说就是指有两个限定条件的背包问题
1.第一题
画图分析
本题目简单来说，就是从数组中挑选字符串，挑出来的字符串要共同满足1和0 的最多出现次数的条件，因此是一个背包问题，且要满足两个条件，因此是二维费用的背包问题
使用动态规划解决
1.状态表示
dp[i][j][k]表示从前i个字符串中挑选，字符0的个数不超过j,字符1的个数不超过k,所有的选法中最大的长度
2.状态转移方程
3.初始化 对于三维的也一样，仅需初始化关于i=0的这些数据，根据状态表示，都初始化为1
4.填表顺序 i从小到大
5.返回值 dp[len][m][n]
具体代码
int findMaxForm(vector<string>& strs, int m, int n)
{
int len=strs.size();
vector<vector<vector<int>>>dp(len+1,vector<vector<int>>(m+1,vector<int>(n+1)));
for(int i=1;i<=len;++i)
{
//统计字符串中0 1的个数
int a=0,b=0;
for(auto ch:strs[i-1])
{
if(ch=='0') ++a;
else ++b;
}
for(int j=0;j<=m;++j)
{
for(int k=0;k<=n;++k)
{
dp[i][j][k]=dp[i-1][j][k];
if(j>=a && k>=b) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-a][k-b]+1);
}
}
}
return dp[len][m][n];
}
//优化
int findMaxForm(vector<string>& strs, int m, int n)
{
int len=strs.size();
vector<vector<int>>dp(m+1,vector<int>(n+1));
for(int i=1;i<=len;++i)
{
//统计字符串中0 1的个数
int a=0,b=0;
for(auto ch:strs[i-1])
{
if(ch=='0') ++a;
else ++b;
}
for(int j=m;j>=a;--j)//从大到小
{
for(int k=n;k>=b;--k)
{
dp[j][k]=max(dp[j][k],dp[j-a][k-b]+1);
}
}
}
return dp[m][n];
}2.第二题
画图分析：
会发现这个问题也是从这个表中选取对应的数据，来满足一定条件的需求，且每个位置只有选与不选的情况，满足两个条件，因此是二维费用的01背包问题
1.状态表示
dp[i][j][k]表示在前i个工作中挑选，总人数不超过j,总利润至少为k,一共有多少中选法
2.状态转移方程
3.初始化 初始化情况为从前0中挑选，此时不管怎么挑利润都是0，但挑选出来的空集也是一种方法，即初始化为1 dp[0][j][0]=1(0<=j<=n)
4.填表顺序 i从小到大
5.返回值 dp[len][n][m]
具体代码：
int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p)
{
const int MOD=1e9+7;
int len=g.size();
vector<vector<vector<int>>> dp(len+1,vector<vector<int>>(n+1,vector<int>(m+1)));
for(int j=0;j<=n;++j) dp[0][j][0]=1;
for(int i=1;i<=len;++i)
{
for(int j=0;j<=n;++j)
{
for(int k=0;k<=m;++k)
{
dp[i][j][k]=dp[i-1][j][k];
if(j>=g[i-1])
dp[i][j][k]+=dp[i-1][j-g[i-1]][max(0,k-p[i-1])];
dp[i][j][k]%=MOD;
}
}
}
return dp[len][n][m];
}
//优化后
int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p)
{
const int MOD=1e9+7;
int len=g.size();
vector<vector<int>>dp(n+1,vector<int>(m+1));
for(int j=0;j<=n;++j) dp[j][0]=1;
for(int i=1;i<=len;++i)
{
for(int j=n;j>=g[i-1];--j)
{
for(int k=m;k>=0;--k)
{
dp[j][k]+=dp[j-g[i-1]][max(0,k-p[i-1])];
dp[j][k]%=MOD;
}
}
}
return dp[n][m];
}2.其余杂题
画图分析：
使用动态规划解决
既然不能使用背包问题的解决方法的话，那就使用根据分析问题的过程中，发现重复子问题，抽象出来一个状态表示
初始化 秩序初始化dp[0]即可，根据状态表示，初始化为1
填表顺序 从左往右
返回值 dp[target]
具体代码：
int combinationSum4(vector<int>& nums, int target)
{
vector<double> dp(target+1);
dp[0]=1;
for(int i=1;i<=target;++i)
for(auto x:nums)
{
if(i>=x) dp[i]+=dp[i-x];
}
return dp[target];
}2.第二题
画图分析：
使用动态规划解决
1.状态表示 根据分析问题的过程中，发现重复子问题，抽象出来一个状态表示
3.初始化 根据状态表示初始化dp[0](空树)为1即可
4.填表顺序 从左往右
5.返回值 dp[n]
具体代码：
int numTrees(int n)
{
vector<int> dp(n+1);
dp[0]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
dp[i]+=dp[j-1]*dp[i-j];
return dp[n];
}