动态规划

• 如果涉及到i - 1这种下标，状态表示从索引1开时，索引0设置成边界
• 时间复杂度：状态数量 * 转移计算量

背包问题

1. 0-1背包

• 每个物品只有一个

• 状态定义：f(i, j)

  • 集合：所有从前i种物品中选，总重量为j的集合（i和j是下标）
  • 属性：该集合中各种情况的最大价值（元素的值）

• 状态计算：f(i, j) = max( f(i - 1, j), f(i - 1,j- V_i) + W_i )

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++ ) cin >> 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]);
        }
    }
    
    cout << f[n][m] << endl;
    return 0;
}

//用滚动数组优化空间复杂度
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++ ) { //依次枚举物品
        for(int j = m; j >= v[i]; j -- ) { //从大到小枚举，因为状态转移时计算当前值需要上一层的值，所以从后往前算，保证计算第i层的f[j]时，f[j - v[i]]中存储的是还没有被更新过的上一层的值，即二维状态表示中的f[i - 1][j -v[i]],而不是f[i][j - v[i]]
			f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    return 0;
}

2.完全背包

• 状态表示：f(i, j)
  • 集合：所有只考虑前i个物品，且总体积不大于j的选法
  • 属性：集合中各种选法的最大价值
• 状态计算： f[i][j] = max(f[i - 1][j - v[i] * k] + w[i] * k)

//朴素做法(评测系统超时)
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            for(int k = 0; k * v[i] <= j; k ++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);//第i个物品选k个
            
    cout << f[n][m];
    
    return 0;
}

//优化做法
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    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 <= m; j ++ )
            f[j] = max(f[j], f[j - v[i]] + w[i]); //因为总体积是从小到大递推，所以在计算选择k个i物品的价值时，选择k - 1个i物品的价值已经被计算过了，而且被更新到了f[j - v[i]]中  就像要信任递归一样，也要信任自己的递推公式
            
    cout << f[m];
    
    return 0;
}

3. 多重背包

• 每件物品的个数是有限制的

• 状态表示：f(i, j)

  • 集合：所有只从前i个物品中选，并且总体积不超过j的选法
  • 属性：集合中所有选法的最大价值

• 状态计算： f[i][j] = max(f[i - 1][j - v[i] * k] + w[i] * k) k = 0, 1, 2, ..., s[i]

//朴素版本， 时间复杂度O(n^3)
#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            for(int k = 0; k * v[i] <= j && k <= s[i]; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
                
    cout << f[n][m] << endl;
    
    return 0;
}

//优化写法
//二进制优化：将每种物品按照指数级进行分组拆分，并将拆分后的各个组“包装”成“新的物品”，只要拆分策略保证拆分后新的物品能拼凑出原来物品能取到的物品个数比，那么完全可以将新问题当作0-1背包问题来处理
//朴素版本， 时间复杂度O(n^3)
#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            for(int k = 0; k * v[i] <= j && k <= s[i]; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
                
    cout << f[n][m] << endl;
    
    return 0;
}

4. 分组背包问题

• 状态表示：f(i, j)
  • 集合：只从前i种物品中选，并且总体积不大于j的所有选法
  • 属性：集合中所有选法的最大价值
• 状态计算：f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i, k]] + w[i, k])

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main() {
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++ ) {
        cin >>  s[i];
        for(int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    } 
    
    for(int i = 1; i <= n; i ++ )//枚举分组
        for(int j = m; j >= 0; j -- )//枚举总体积
            for(int k = 0; k <= s[i]; k ++ )//在每个分组内枚举“组员”
                if(v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);//类似0-1背包问题的思路，最后的不同点是“选不选第i组中的第k个物品”
                    
    cout << f[m] << endl;
            
    return 0;
}

线性DP

5. 数字三角形

• 状态表示：f(i, j)
• 集合：所有从起点，走到(i, j)的路径
• 属性：所有这些路径上面数字之和的最大值
• 状态计算： f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j]

//从顶到底
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;
int n;
int a[N][N];
int f[N][N];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= i; j ++ ) {
            cin >> a[i][j];   
        }
    }
    
    for(int i = 0; i <= n; i ++ )
        for(int j = 0; j <= i + 1; j ++ )
            f[i][j] = -INF;
            
    f[1][1] = a[1][1];
    for(int i = 2; i <= n; i ++ ) 
        for(int j = 1; j <= i; j ++ )
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
            
    int res = -INF;
    for(int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    
    cout << res << endl;
    
    return 0;
}

//从底到顶

6.最长上升子序列

• 状态表示：f[i]
  • 集合：所有以第i个数结尾的上升子序列
  • 属性：所有以第i个数结尾的上升子序列的最大长度
• 状态计算：按照倒数第二个数是哪个数来对集合分类 : f[i] = f[j] + 1 j = 0, 1,2,...,i - 1

//朴素版本
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    
    for(int i = 1; i <= n ; i ++ ) {
        f[i] = 1; //只有i一个数
        for(int j = 1; j < i; j ++ )
            if(a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    
    int res = 0;
    for(int i = 1; i <= n; i ++ ) res = max(res, f[i]);
    
    cout << res << endl;
    
    return 0;
}

//优化版本

7. 最长公共子序列

• 状态表示：f[i][j]
  • 集合：所有在第一个序列的前i个字母中出现，且在第二个序列的前j个字母中出现的子序列
  • 属性：集合中子序列长度的最大值
• 状态计算：划分依据，a[i] 和b[j]是否包含在公共子序列中，划分为4个子集 f[i][j] = max(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] + 1) 注意这个递推式的中间两部分和划分子集不完全对应，也就是说四种情况之间有重叠，但是由于求最大值，重复不影响结果；上述递推式可以进一步化简为 f[i][j] = max(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] + 1)， 因为第一种子类的情况一定包含于第二种或者第三种子类当中

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {
    cin >> n >> m;
    scanf("%s%s", a + 1, b + 1);
    
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= m; j ++ ) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j]) f[i][j] = max(f[i - 1][j - 1] + 1, f[i][j]);
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

8. 编辑距离

• 状态表示：
  • 集合：
  • 属性：
• 状态计算：

区间DP

9. 石子合并

• 状态表示：f[i][j]
  • 集合：所有将第i堆石子到第j堆石子合并成一堆的方式
  • 属性：所有这些合并方式的最小代价
• 状态计算：最后一次合并一定是将两堆石子合并成一堆，所以可以按照最后一次合并时的分界线来分类， f[i][j] = min(f[i][k] + f[k + 1][j] + s[j] - s[i - 1]), k = i ~ j - 1

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> s[i];
    
    for(int i = 1; i <= n; i ++ ) s[i] += s[i - 1];
    
    for(int len = 2; len <= n; len ++ ) //枚举区间长度
        for(int i = 1; i + len - 1 <= n; i ++ ) { //枚举起点
            int l = i, r = i + len - 1;
            f[l][r] = 2e9;
            for(int k = l; k < r; k ++ )//枚举分界点
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
        
    cout << f[1][n] << endl;
    
    return 0;
}

刷题总结（五）| 动态规划2——常见题型整理

原文：https://www.cnblogs.com/huhu555/p/14628115.html