动态规划DP有着很高的上限，难的DP所要写的转移方程往往很难想想到，下面博主简单介绍一下基础的DP
首先便是大家熟知 但对于初学者又比较困难的背包问题
这里简单介绍一下01背包
杭电2602
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[1006];
int b[1006];
int dp[1006][1006];
int n,m;
int t;
int main() {
scanf("%d",&t);
while(t--) {//多组输入
scanf("%d%d",&n,&m);
memset(dp,0,sizeof(dp));//多组输入的初始化！
int i,j;
for (i=1; i<=n; i++)
scanf("%d",&a[i]);
for (j=1; j<=n; j++)
scanf("%d",&b[j]);//输入
// for (i=1;i<=n;i++)
// printf("%d",a[i]);
// for (j=1;j<=n;j++)
// printf("%d",b[i]);
for (i=1; i<=n; i++) {
for (j=0; j<=m; j++) {
if (j>=b[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-b[i]]+a[i]);//转移方程 动态规划的核心
else
dp[i][j]=dp[i-1][j];
}
}//重点解释
// for (i=1; i<=n; i++)
// for (j=1; j<=m; j++) {
// if (j==m)
// printf("%d\n",dp[i][j]);
// else
// printf("%d ",dp[i][j]);
// }
printf("%d\n",dp[n][m]);
}
return 0;
}看到这里很多萌新就要问了，我还是看不懂怎么办
下面博主就对代码中的重要部分解释。
我们定义一个二维数组DP[i][j];
其中i表示第i个物品 ，j表示当前所需的容量 而DP[i][j]的值就是当前背包所装物品的总价值
那我们需要怎样实现转移呢
如题目样例
1
5 10
1 2 3 4 5
5 4 3 2 1
我们从第一个物品开始
选择放入和不放入 （在这里有萌新要问了，怎么不放入呢）
ps：其实很简单 比如第一个物品 重5价值1；我们在背包中，背包容量小于5的是放不下的，这其实就代表着放和不放，因为第一个物品放入之后是优先在刚好适合的位置放入的，并不会影响下一个的放入
上图：
比如 第一个物品的放入 只能在背包容量大于5
而第二个物品的放入能在大于4，对于第二个物品，如果想在放入第一个物品之后放第二个物品 则需要从背包中空出第二个物品的容量 所以就只能选用既能放下第一个又能放下第二个的背包
（背包容量为9的背包可以放入大小为5 和大小为4 的物品 容量为10 的当然也可以）
而那些容量小于4的就是没有放入第二个物品
同样的对于第三个物品 要从能放入第三个物品的容量大小的背包开始放入 以此类推。
这样我们便可以做到对于每个物品选择放入和不放入 放入的话便从最小所需容量开始放入
于是我们便能退出转移方程 对于第i个物品 如果我们想要放入 那么dp[i][j]=dp[i-1][j-a[i]]+b[i];
dp[i-1][j-a[i]]便是上一个能放入第i个物品背包 在此背包中放入第i个物品 ，然后所包含的价值加上第i个物品的价值;
转移方程写出来了 题目就很简单了
博主对于DP的理解是 ，DP是一种很高级记忆化搜索 ，高级到什么程度呢，高级每搜一步，就需要将搜索的结果储存到DP数组中，然后利用搜索的结果进行下一次搜索 然后继续储存。
是不是很高级呢？
