算法设计与分析 | 动态规划

算法简介

动态规划（Dynamic Programming，简称DP）是一种通过把原问题分解为相互重叠的子问题，并仅仅解决每个子问题一次，将其解保存在一个表格中，从而避免重复计算，提高效率的算法思想。

动态规划的基本思想可以概括为以下几个步骤：

1. 划分子问题： 将原问题划分为若干个规模较小的子问题。

2. 解决子问题： 递归地或迭代地求解子问题。通常，通过保存子问题的解避免重复计算。

3. 合并子问题的解： 将子问题的解组合起来，得到原问题的解。

同时，在使用动态规划时，需注意问题的以下两个性质：

1. 重叠子问题（Overlapping Subproblems）： 原问题可以分解为若干个相同的子问题。解决这些子问题只需要一次计算，并将结果存储以避免重复计算。

2. 最优子结构（Optimal Substructure）： 问题的最优解可以通过子问题的最优解推导出。

例题两道

1. 0-1背包问题

问题描述：有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。第 i 件物品的体积是 v_i，价值是 w_i。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

题解：

初始化f数组的第i行第j列为背包容量为j的情况下在前i件物品中可装入的最大价值，对背包容量（列）进行遍历，对物品（行）进行动态规划，具体如下：

• 若j大于当前物品容量，则选择是否加入此物品；
• 否则，不能加入此物品；

时间复杂度为O(n×v)，c++代码如下：

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int n, v;
    cin >> n >> v;
    int volume[n], money[n];
    int f[n+1][v+1] = {0};
    for(int i = 1; i <= n; i++)
        cin >> volume[i] >> money[i];
    int value = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= v; j++) {
            if(j >= volume[i]) 
                f[i][j] = max(f[i-1][j], f[i-1][j-volume[i]] + money[i]);
            else
                f[i][j] = f[i-1][j];
        }
    cout << f[n][v] << endl;
    return 0;
}

2. 最大子矩形问题

问题描述：给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为 1×1或更大的连续子阵列。矩形的总和是该矩形中所有元素的总和。在这个问题中，具有最大和的子矩形被称为最大子矩形。

题解：

初始化sum数组的第i行第j列为二维矩阵第i行第0位到第j位的和sum[i][j] = sum[i][j-1] + matrix[i][j]，对列进行遍历，对行进行动态规划，具体如下：

• k、j为列标，表示遍历（k，j）列的内容；
• i为行标，表示是否加上第i行第（k，j）列的和；

最后取最大值即可，时间复杂度为O(n^3)，c++代码如下：

#include<bits/stdc++.h>

using namespace std;
int main(){
    int n;
    cin >> n;
    int matrix[n+1][n+1], sum[n+1][n+1] = {0};
    for(int i = 1; i < n+1; i++)
        for(int j = 1; j < n+1; j++){
            cin >> matrix[i][j];
            sum[i][j] = sum[i][j-1] + matrix[i][j];
        }
    int ans = -1000;
    for(int j = 1; j <= n ; j++)
        for(int k = 0; k < j; k++){
            int temp = 0;
            for(int i = 1; i <= n; i++){
                temp = max(sum[i][j] - sum[i][k], temp + sum[i][j] - sum[i][k]);
                ans = max(ans,temp);
            }
        }
    cout<<ans<<endl;
    return 0;     
}