Noote:

分组背包: f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]);

//分组背包
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int f[N][N]; //状态定义数组 初始值因为全局都是0了
int v[N], w[N]; //用来接收每个物品的体积和价值

int n, m, a, b; //表示物品个数 背包体积 a是物品i的体积 b是价值

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> v[i] >> w[i];
    }
    /*
        01背包的二维状态转移方程
        不选 f[i][j] = f[i-1][j];
        选(在体积够的情况下) f[i][j] = f[i-1][j-v[i]] + w[i];
        f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])
    */
    //物品从1开始 0个物品价值为0
    for(int i = 1; i <= n; ++i)
        //因为要保证背包容量是大于物品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]);
        }
    cout << f[n][m] << endl;
    system("pause");
    return 0;
}

区间DP

区间dp：就是对于区间的一种动态规划，对于某个区间，它的合并方式可能有很多种，我们需要去枚举所有的方式，通常是去枚举区间的分割点，找到最优的方式(一般是找最少消耗)。

例如：对于区间【i，j】，它的合并方式有很多种，可以是【i，i+1】和【i+2，j】也可以是【i，k】和【k+1，j】（其中i <= k < j）……