c++动态规划经典算法

c++动态规划经典算法攻略

什么是动态规划

动态规划（Dynamic Programming，DP）是一种解决多阶段决策问题的优化算法，其本质是将原问题分解为若干个子问题，同时记录下每个子问题的最优解，以便于后续利用。

动态规划通常由三个步骤构成：

1. 定义状态，即确定子问题的规模和状态表示；
2. 状态转移，即确定子问题之间的转移关系，从而将问题规模缩小；
3. 确定边界条件，即确定最小子问题的解，以便于递推过程中能够终止。

动态规划的经典算法

01背包问题

假设有一个背包和 $n$ 个物品，第 $i$ 个物品的价值是 $v_i$，重量是 $w_i$。问最多可以装多少价值的物品？

下面是一个例子：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int n, c, w[N], v[N], f[N][N];

int main() {
    cin >> n >> c;

    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= c; j++)
            if (j >= w[i])
                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
            else
                f[i][j] = f[i - 1][j];

    cout << f[n][c] << endl;

    return 0;
}

其中，$f_{i,j}$ 表示前 $i$ 件物品恰好填满容量为 $j$ 的背包所获得的最大价值。该算法的时间复杂度是 $O(n*w)$。

最长上升子序列

给定一个序列 $a$，求其中最长的上升子序列的长度。例如，对于序列 $a = {2, 9, 3, 6, 5, 1, 7}$，其中最长的上升子序列是 ${2, 3, 5, 7}$，长度为 $4$。

下面是一个例子：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int n, a[N], f[N], ans = 1;

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]);
    }

    cout << ans << endl;

    return 0;
}

其中，$f_i$ 表示以 $a_i$ 结尾的最长上升子序列的长度。该算法的时间复杂度是 $O(n^2)$。

总结

以上是动态规划的两个经典算法，它们适用于多种场景的问题。掌握动态规划算法，可以提高算法解题的效率，成为一名优秀的算法工程师。