动态规划

定义

动态规划(英语: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$

Last modification:October 4th, 2020 at 09:08 pm
如果您觉得我的文章有用,给颗糖糖吧~