DP总结

DP(动态规划)简介
动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

DP基础

1.必要前提
需要满足三个条件：最优子结构，无后效性和子问题重叠。

2.基本思路

1. 将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
2. 寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
3. 按顺序求解每一个阶段的问题。

各种DP

1. 背包DP
   1. 01背包!
      

      • 朴素版

        点击查看代码

        #include <bits/stdc++.h>
        using namespace std;
        const int maxn = 1010;
        //f[i][j]表示前i个物品，体积不超过j时的最大价值
        //不选第i个物品时，f[i][j] = f[i-1][j]
        //选第i个物品时，f[i][j] = f[i-1][j-v[i]]+w[i],保证j>=v[i] 
        int f[maxn][maxn] = {};	//默认全为0，这样后面就不需要再初始化
        int n = 0, m = 0;	//n件物品，m为背包总容量
        int v[maxn] = {}, w[maxn] = {};	//v表示第i件物品体积，w为第i件物品价值
        int main()
        {	
        	scanf("%d%d", &n, &m);
        	for(int i=1; i<=n; i++) scanf("%d%d", &v[i], &w[i]); 
        	for(int i=1; i<=n; i++)
        	{
        		for(int j=0; j<=m; j++)
        		{
        			f[i][j] = f[i-1][j];
        			if(j>=v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
        		}
        	}
        	printf("%d", f[n][m]);
        	return 0;
        }
        
        

      • 滚动数组优化版 因为每次的动态转移只与i-1层（前i-1个物品）的dp值相关 所以可用二维数组模拟滚动数组以减少内存

      • 终极版
        我们发现物品枚举顺序跟结果无关，枚举体积时先枚举体积大的还是小的也不影响最后结果，如果我们枚举体积的时倒序枚举，那在第二层循环中（j）f[j]之前的位置（f[1]~f[j-1]）都是在选前i-1件物品是的无后效性的dp值，这样我们就可以省去一维数组，我们用f[j]表示处理当前第i件物品时体积为j的最大价值，
        递推公式：f[j]=max(f[j],f[j-v[i]]+w[i])。表达式右边的f[j],f[j-v[i]]表示处理完上个物品之后的结果，由于倒序处理处理体积j的时候f[j]， f[j-v[i]]还保留着上一行的状态

        点击查看代码

        #include <bits/stdc++.h>
        using namespace std;
        const int maxn = 1010;
        int f[maxn] = {};	//默认全为0，这样后面就不需要再初始化
        int n = 0, m = 0;	//n件物品，m为背包总容量
        int v[maxn] = {}, w[maxn] = {};	//v表示第i件物品体积，w为第i件物品价值
        int main()
        {	
        	scanf("%d%d", &n, &m);
        	for(int i=1; i<=n; i++) scanf("%d%d", &v[i], &w[i]); 
        	for(int i=1; i<=n; i++)
        	{
        		for(int j=m; j>=v[i]; j--)
        		{ 
        			f[j] = max(f[j], f[j-v[i]] + w[i]);
        		}
        	}
        	printf("%d", f[m]);
        	return 0;
        }