动态规划

定义

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

要求

试用动态规划解决问题，需要问题满足下列要求：

最优子结构性质，即全局最优解包含的子问题的解也是最优解。
无后效性，即前面的决策不收后面影响。
子问题重叠性质。这也是 DP 可以比爆搜快的原因。

常见模板

最长上升子序列

给定一个长度为 $n$ 的序列 A，求最长上升子序列的长度。$n \leq 1000$。

最长公共子序列

点击此处以访问模板提交链接。

给出 $1, 2, \ldots, n$的两个排列 $P_1$ 和 $P_2$，求它们的最长公共子序列。

$n,m \leq 3\times 10^3$

#include <bits/stdc++.h>
using namespace std;
int a[100001], b[100001], mmp[100001], f[100001];
int main() {
    ios::sync_with_stdio( false );
    int n;
    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        cin >> a[i];
        mmp[a[i]] = i;
    }
    for ( int i = 1; i <= n; i++ ) {
        cin >> b[i];
        f[i] = INT_MAX;
    }
    int len = 0;
    f[0] = 0;
    for ( int i = 1; i <= n; i++ ) {
        int l = 0, r = len, mid;
        if ( mmp[b[i]] > f[len] ) {
            f[++len] = mmp[b[i]];
        }
        else {
            while ( l < r ) {
                mid = ( l + r ) / 2;
                if ( f[mid] > mmp[b[i]] ) {
                    r = mid;
                }
                else {
                    l = mid + 1;
                }
            }
            f[l] = min( mmp[b[i]], f[l] );
        }
    }
    cout << len << endl;
    return 0;
}

背包

01背包

$n$ 种物品，每一个物品有一个价值 $v$ 和一个体积 $w$ ，你有一个大小为 $m$ 的背包，你需要装进去最大价值的物品。

$n, m \leq 10^3$

版权声明：本文是原创文章，版权归星雾月雨所有。
本文链接：https://www.ariels.xyz/archives/859.html
本站所有下方标记为「允许规范转载」的原创文章均采用署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。

动态规划整理