分享｜动态规划类问题综述及解法

2054

2023.04.02

发布于未知归属地

动态规划类问题

动态规划的介绍

动态规划问题（Dynamic Programming）俗称DP问题

但是动态规划算法既不”动态“也没有”规划“。这个算法的名字与算法本身联系不大。

关于动态规划算法名称，贝尔曼(Bellman)在他的自传中这样介绍:
The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, "programming". I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.[1]

实际上，与贪心算法求解局部最优解相对，动态规划算法用于求解某种整体最优性质的多阶段决策问题。所以我们在理解动态规划问题时不能被它的名字所蒙蔽！

动态规划的应用场景

举一个简单的例子

我们在初学算法的时候一定都用递归写过斐波那契数列

{1,1,2,3,5,8,13...}

Fibonacci (n) = 1;   n = 0
Fibonacci (n) = 1;   n = 1
Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2)

我们很容易就可以把它用代码实现

int Fibonacci(int n)
{
    if(n==1||n==2) return 1;
    else return Fibonacci(n-1)+Fibonacci(n-2);
}

现在有一个问题：当我们求解这个斐波那契数列的第六项元素时
存在有下面的递归搜索树
递归搜索树.png
我们发现在这个递归搜索树中，有很多重复递归调用的部分（比如fib(2)一共被调用了5次）。如果在第一次调用到时就将该元素存储下来，在再次递归调用时直接查表就可以节省很多的时间。

那么在什么情况下应该使用动态规划方法求解问题呢？

动态规划方法应用要素

最优子结构
子问题重叠

最优子结构

最优子结构性质：

如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质

重叠子问题

重叠子问题性质：

子问题的空间必须足够”小“，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。(与之相对的，适合用分治策略求解的问题通常在递归的每一步都生成全新的子问题）动态规划算法通常这样利用重叠子问题性质：对每个问题求解一次，将解存入一个表中，当再次需要这个子问题时直接查表，每次查表得代价为常量空间。[2]

动态规划的基本原理

闫式DP分析法

闫式DP分析法是一种利用集合的角度来解决动态规划问题的方法
从两个角度来解决：状态表示，状态计算 [3]

状态表示 f[i][j] (化整为零)

集合

根据具体问题通过一个数组来表示相应集合的状态

属性

一般有三种：最大值（max），最小值（min），数量（count）

状态计算——集合的划分

根据动态规划类问题具有重叠子问题的性质可以将集合进行划分
划分的集合可以有重叠相交的部分但划分之后的子集交集必须为全集

优化

状态转移方程可以通过递推性质优化
可以结合其他算法如：二分查找，哈希来进行优化

动态规划的经典模型

背包模型

给定一组物品每件物品都有自己的体积（重量）和价值
在限定的体积（重量下）我们如何选择，使得物品的总价值最大

0-1背包问题

每个物品最多用一次

状态表示 $f [i] [j]$ (化整为零)
$f [i] [j]$ 表示集合的属性
通过一个数组来表示只从前 $i$ 个物品中选择，且总体积不超过 $j$ 时的最大价值

属性：背包中元素的最大值（max）

状态计算——集合的划分（化零为整）

将集合划分为两类集合

不包含第 $i$ 个物品（从前 $i - 1$ 个物品中选）
包含第 $i$ 个物品

所有不包含第 $i$ 个物品时

$f [i] [j]$ 表示从前 $i$ 个物品中选，但是此时将集合划分，该部分不包含第 $i$ 个元素
此时的集合的属性是和 $f [i - 1] [j]$ 等价的

所有包含第 $i$ 个物品时

$f [i] [j]$ 表示从前 $i$ 个物品中选择的总价值最大，且一定包含第 $i$ 个物品的方案
那么我们可以将第 $i$ 个物品抽离出来
$f [i] [j]$ 就等价于 $f [i - 1] [j] + w [i]$
也就是说从前 $i$ 个物品中选出总价值最大的方案等于从前 $i - 1$ 个物品中选，总价值最大的方案加上第 $i$ 个物品的价值

状态转移方程：

$f [i] [j] = ma x (f [i - 1] [j], f [i - 1] [j - v [i]] + w [i])$

0-1背包问题.png

C++代码

#include<bits/stdc++.h>

using namespace std;

const int N=1010;
int f[N][N]; //f[i][j]表示从前i个物品中选且总体积不超过j的物品的最大价值
int v[N],w[N]; //v[i]存储第i个物品的体积，w[i]存储第i个物品的价值

int main()
{
    int n,m;
    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; //输出从前n个物品中取且总体积不超过m的最大价值
    
    return 0;
}

$空间优化 :$

为什么可以转化为一维呢？

先回到对状态表示数组 $f [i] [j]$ 的定义
$f [i] [j]$ 表示前选取 $i$ 个物品且最大体积不超过 $j$ 的最大价值
而我们想要知道的是总体积不超过 $j$ 时所有物品装入背包的最大价值
当我们去掉 $f [i] [j]$ 的第一维后
$f [j]$ 恰好是总体积不超过 $j$ 的最大价值
再看状态转移方程：
$f [i] [j] = ma x (f [i - 1] [j], f [i - 1] [j - v [i]] + w [i])$
循环时，每次只用 $i$ 更新 $i - 1$ 而不会用到 $i - 2$ 以及之前的值
对于 $i$ 的更新，我们直接使用一维数组覆盖掉就可以了

如何转化为一维呢？

值得注意的是
区别于二维状态下的正序枚举，一维状态下枚举是逆序的
简单理解一下，优化到一维后 $f [j]$ 表示总体积不超过 $j$ 的最大价值
正序枚举时：当我们选择从较小体积枚举到较大体积时
由于缺乏一维无法约束挑选物品的状态
对于每次 $j$ 的更新
每次用到的是 $i - 1$ 或者是 $j - v [i]$ 的数据
正序枚举时，会将后续数据依次更新，不能保证原来 $i - 1$ 时的状态来更新 $i$ 的状态
逆序枚举时，更新 $i$ 不会影响到 $i - 1$

当前枚举的背包容量下，该物品不选择时，与前 $i - 1$ 个物品状态结果相同，不需要改变
当前枚举的背包容量下，该物品被选择时，与前 $i - 1$ 个物品取最大值

状态转移方程：

$f [j] = ma x (f [j], f [j - v [i]] + w [i])$

C++代码

#include<bits/stdc++.h>

using namespace std;

const int N=1010;
int f[N]; //f[i][j]表示从前i个物品中选且总体积不超过j的物品的最大价值
int v[N],w[N]; //v[i]存储第i个物品的体积，w[i]存储第i个物品的价值

int main()
{
    int n,m;
    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]); //状态转移方程
        }
    }
    
    cout<<f[m]<<endl; //输出从前n个物品中取且总体积不超过m的最大价值
    
    return 0;
}

完全背包问题

每个物品理论上可以重复使用无限次

状态表示 $f [i] [j]$ (化整为零)
$f [i] [j]$ 表示集合的属性
通过一个数组来表示只从前 $i$ 个物品中选择，且总体积不超过 $j$ 时的最大价值

属性：背包中元素的最大值（max）

状态计算——集合的划分（化零为整）

将集合划分为 $k$ 个集合
对于集合 $f [i] [j]$

不包含第 $i$ 个物品（从前 $i - 1$ 个物品中选）
包含一个第 $i$ 个物品
包含两个第 $i$ 个物品
......
包含 $k$ 个第 $i$ 个物品

状态转移方程：

$f [i] [j] = ma x (f [i - 1] [j], f [i] [j - k \times v [i]] + k \times w [i])$

完全背包问题朴素做法.png

$优化 :$

我们知道完全背包的状态转移方程是：
$f [i] [j] = ma x (f [i - 1] [j], f [i] [j - k \times v [i]] + k \times w [i])$
我们假设 $v = v [i], w = w [i]$
代入上式后，实际上等价于：
$f [i] [j] = ma x (f [i - 1] [j], f [i] [j - v] + w, f [i] [j - 2 v] + 2 w, f [i] [j - 3 v] + 3 w, ......)$
我们观察到这个公式存在递推性
那么我们写出下一项
$f [i] [j - v] = ma x (f [i - 1] [j - v], f [i] [j - 2 v] + w, f [i] [j - 3 v] + 2 w, f [i] [j - 4 v] + 3 w, ......)$
此时我们可以惊奇的发现前后两项存在这样的递推关系
$f [i] [j] = ma x (f [i - 1] [j], f [i] [j - v] + w)$
回代 $v = v [i], w = w [i]$ 得
$f [i] [j] = ma x (f [i - 1] [j], f [i] [j - v [i]] + w [i])$
这样在代码中就可以减少一重对划分集合时讨论第 $i$ 个元素个数的循环

C++代码

#include<bits/stdc++.h>

using namespace std;

const int N= 1010;

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

int main()
{
    int n,m;
    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][j-v[i]]+w[i]);
            }
        }
    }
    
    cout<<f[n][m]<<endl;
    
    return 0;
}

多重背包问题

问题介于0-1背包问题和完全背包问题之间
每个物品的个数为有限个
实际上分析时与完全背包问题非常类似

状态表示 $f [i] [j]$ (化整为零)
$f [i] [j]$ 表示集合的属性
通过一个数组来表示只从前 $i$ 个物品中选择，且总体积不超过 $j$ 时的最大价值

属性：背包中元素的最大值（max）

状态计算——集合的划分（化零为整）

将集合划分为 $k$ 个集合
对于集合 $f [i] [j]$ 我们将其划分为：

不包含第 $i$ 个物品（从前 $i - 1$ 个物品中选）
包含一个第 $i$ 个物品
包含两个第 $i$ 个物品
......
包含 $k$ 个第 $i$ 个物品 $(k \leq s [i])$

状态转移方程：

$f [i] [j] = ma x (f [i - 1] [j], f [i] [j - k \times v [i]] + k \times w [i])$

多重背包问题.png

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N=110;
int v[N],w[N],s[N];
int f[N][N];

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

但是这是一种效率较低的算法

$优化 :$

我们先从状态转移方程入手：
$f [i] [j] = ma x (f [i - 1] [j], f [i] [j - k \times v [i]] + k \times w [i])$
联想到上面完全背包问题中我们所做的优化
便有如下尝试：
我们假设 $v = v [i], w = w [i], s = s [i]$
代入上式后，实际上等价于：
$f [i] [j] = ma x (f [i - 1] [j], f [i] [j - v] + w, f [i] [j - 2 v] + 2 w, f [i] [j - 3 v] + 3 w, ......, f [i] [j - s \times v] + s \times w)$
类似地，我们写出下一项
$f [i] [j - v] = ma x (f [i - 1] [j - v], f [i] [j - 2 v] + w, f [i] [j - 3 v] + 2 w, f [i] [j - 4 v] + 3 w, ......, f [i] [j - s \times v] + (s - 1) \times w, f [i] [j - s \times (s + 1) \times v] + s \times w)$
等式左右两边同时加上 $w$ 后：
$f [i] [j - v] + w = ma x (f [i - 1] [j - v] + w, f [i] [j - 2 v] + 2 w, f [i] [j - 3 v] + 3 w, f [i] [j - 4 v] + 4 w, ......, f [i] [j - s \times v] + s \times w, f [i] [j - s \times (s + 1) \times v] + (s + 1) \times w)$
但是，通过对照，我们发现最后多了一项
$f [i] [j - s \times (s + 1) \times v] + (s + 1) \times w)$
在最大值中
我们无法”减去“其中一项求得剩余元素的最大值
因此，使用刚才的优化思路是行不通的

此时我们采用 $二进制优化$ 的方法

核心思路：就是将每个物品根据自身的数量进行打包处理

假设第 $i$ 个物品一共有1023个 $(s = 1023)$

我们可以将第 $i$ 个物品打包为不同数量的集合

1个第 $i$ 个物品为一组，2个第 $i$ 个物品为一组，4个第 $i$ 个物品为一组......一直到512个第 $i$ 个物品为一组，每个组只能被选择一次

此时我们在选择第 $i$ 个物品装入背包的个数时
可以表示出 $0 - 1023$ 个第 $i$ 个物品的情况

简单证明:

当我们选择一组时（1( $2^{0}$ )个第 $i$ 个物品）
可以表示出 $[0, 1]$ 这个区间内个数的第 $i$ 个物品
当我们选择前两组时（2( $2^{1}$ )个第 $i$ 个物品）
可以表示出 $[0, 3]$ 这个区间内个数的第 $i$ 个物品
同理，当我们选择前三组时（4( $2^{2}$ )个第 $i$ 个物品）
可以表示出 $[0, 7]$ 这个区间内个数的第 $i$ 个物品
......
当我们挑选前10组时（512( $2^{9}$ )个第 $i$ 个物品）
我们恰好可以表示出的区间的范围恰好是 $[0, 2^{10} - 1]$
（其实就是高中等比数列前 $n$ 项求和）

也就是说
当我们分别将1个第 $i$ 个物品，2个第 $i$ 个物品，4个第 $i$ 个物品，......，512个第 $i$ 个物品分组后
我们可以将背包中装入第 $i$ 个物品的个数情况位于区间 $[0, 1023]$ 全部用新分好的组表示出来

归纳可知：
当我们将物品分为: $1, 2, 4, 8......, 2^{k}$ 个第 $i$ 个物品这样的小组时
我们可以表示出来的包含第 $i$ 个物品的区间恰好是 $[0, 2^{k + 1} - 1]$

这是边界恰好为2的幂时的情况

当边界不是2的幂时，比如说边界是200时 $(s = 200)$

我们将200个第 $i$ 个物品分为
1,2,4,......,64个组
这时答案的区间位于 $[0, 127]$ 内
我们再加上一个组其中包含有73个第 $i$ 个物品
此时恰好可以表示出包含第 $i$ 个物品的区间为 $[0, 200]$

那么对于一个一般的 $s$ 呢？
我们将 $s$ 个第 $i$ 个物品分为下面的几组
1,2,4,8,16,......, $2^{k}$ , $c$
其中 $s - (2^{k + 1} - 1) \leq c < 2^{k + 1}$
如果 $c \geq 2^{k + 1}$ ，那么 $c$ 又成为2的幂次无法凑出任意的一个 $s$ 值
那么当 $c$ 这样取值时，一定可以合并为 $[0, s]$ 这个区间嘛？
我们在规定 $c < 2^{k + 1}$ ,那么严格存在 $c \leq 2^{k + 1} - 1$
此时区间恰好合并为 $[0, s]$

由于我们可以通过不重复的选择由不同个数的第 $i$ 个物品所重新分好的组来组成 $[0, s]$ 区间中任意一个数
此时我们就将该问题转化为0-1完全背包问题

C++代码

#include <bits/stdc++.h>

using namespace std;

const int N = 12010, M = 2010; //数据范围 N=1000log(2000)对数以2为底

int n, m; //n,m分别存储物品总数和背包容积
int v[N], w[N]; //v[i]代表第i组物品的体积，w[i]代表第个物品的体积
int f[M]; //f[j]用来存储总体积不超过j时的最大价值

int main()
{
    cin >> n >> m; //输入物品总数和背包容积

    int cnt = 0; //记录每种物品的分组的个数
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s; 
        cin >> a >> b >> s; //输入第i件物品的体积和价值
        int k = 1; 
        while (k <= s) 
        {
            cnt ++ ;
            v[cnt] = a * k; //将k件第i个物品捆绑作为第cnt件物品
            w[cnt] = b * k; //v[cnt],w[cnt]分别存储其体积和价值
            s -= k; 
            k *= 2; 
        }
        if (s > 0) //s>0说明s件第i个物品未完全打包
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt; //将cnt赋值给n更新物品个数

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]); //0-1背包问题

    cout << f[m] << endl; 

    return 0;
}

我们还可以采取 $单调队列优化 / 二分优化$ 的方法

待补充

分组背包问题

相较于之前的背包问题
在分组背包问题中，给定若干组物品
每组物品有若干个，每组物品中每件物品的体积和价值不一定相同
但同样一组物品中最多只能选一个物品

状态表示 $f [i] [j]$ (化整为零)
$f [i] [j]$ 表示集合的属性
通过一个数组来表示只从前 $i$ 组物品中选择，且总体积不超过 $j$ 时的最大价值

属性：背包中元素的最大价值（max）

状态计算——集合的划分（化零为整）

将集合划分为 $k$ 个集合
类似地，对于集合 $f [i] [j]$ 我们将其同样划分为：

不包含第 $i$ 组物品（从前 $i - 1$ 组物品中选）
包含一个第 $i$ 组物品
包含两个第 $i$ 组物品
......
包含 $k$ 个第 $i$ 组物品 $(k \leq s [i])$

当我们不包含该组物品时，此时的状态应该是 $f [i - 1] [j]$

当我们包含该组物品时，我们从 $[1, s [i]]$ 依次枚举该组物品并更新状态使得总价值最大
此时的状态为 $f [i - 1] [j - v [i] [k]] + w [i] [k]$

状态转移方程：

$f [i] [j] = ma x (f [i - 1] [j], f [i] [j] - v [i] [k] + w [i] [k])$

分组背包问题.png

C++代码

#include<bits/stdc++.h>

using namespace std;

const int N = 110; //数据范围100

int n, m; //输入的n.m值表示物品组数和背包容量
int v[N][N], w[N][N], s[N]; //v表示体积 w表示价值 s表示某组物品中的物品数量
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]);

    cout << f[m] << endl;

    return 0;
}

线性模型

线性DP是在线性结构上进行动态转移的动态规划问题

线性动态规划问题的目标函数为特定变量的线性函数，约束的是这些变量的线性不等式或等式，目的一般是求目标函数的最大值或最小值

数字三角形

原题链接：

洛谷P1216-数字三角形

已知一个由数字构成的三角形如下
要求从顶层走到底层的路径中的数字的和的最大值

        7 
      3   8 
    8   1   0 
  2   7   4   4 
4   5   2   6   5

状态表示 $f [i] [j]$ (化整为零)
$f [i] [j]$ 表示集合的属性
通过一个数组来表示从顶层起点走到(i,j)位置路径中数字之和的最大值

属性：路径下数字之和的最大值（max）

状态计算——集合的划分（化零为整）

将集合划分为2个集合
对于集合 $f [i] [j]$ 我们将其同样划分为：

该路径下的上一个位置来自左上方
该路径下的上一个位置来自右上方

当该路径下，上一个位置来自左上方时
此时的状态应该计算为 $f [i - 1] [j - 1] + a [i] [j]$

当该路径下，上一个位置来自左上方时
此时的状态应该计算为 $f [i - 1] [j] + a [i] [j]$

状态转移方程：

$f [i] [j] = ma x (f [i - 1] [j - 1], f [i - 1] [j] + a [i] [j])$

数字三角形.png

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N=1050,INF=1e9; //数据范围是1000数组开到1050
int a[N][N]; //a[i][j]表示(i,j)位置上所存储的数字
int f[N][N]; //f[i][j]表示从起点到(i,j)位置的路径下的最大值

int main()
{
    int n;
    cin>>n;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            scanf("%d",&a[i][j]); //将数字三角形输入
        }
    }
    
    for(int i=1;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]+a[i][j],f[i-1][j]+a[i][j]); //状态转移方程
        }
    }
    
    int res=-INF; //输出结果最大值的变量
    for(int i=1;i<=n;i++) res=max(res,f[n][i]); //遍历最后一行得到最大值
    
    printf("%d\n",res); //输出结果
    
    return 0;
}

最长上升子序列

原题链接：
LeetCode300-最长递增子序列

最长上升子序列（Longest Increasing Subsequence），简称 $L I S$ ，给定一个长度为 $N$ 的数列，求数值严格单调递增的子序列的长度最长是多少，也有些情况题目要求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。

状态表示 $f [i]$ (化整为零)
$f [i]$ 表示以第i个数结尾的上升子序列

属性：数列中每一个数结尾的所有上升子序列的长度最大值（max）

状态计算——集合的划分（化零为整）

将集合划分为 $i$ 个集合
对于集合 $f [i]$ 我们将其同样划分为：

以 $i$ 结尾的序列中只有 $i$ 这一个元素
以 $i$ 结尾的序列的上一个元素是数列的第一个元素 $n u m s [1]$
以 $i$ 结尾的序列的上一个元素是数列的第二个元素 $n u m s [2]$
...
以 $i$ 结尾的序列的上一个元素是数列的第 $j$ 个元素 $n u m s [j]$
...
以 $i$ 结尾的序列的上一个元素是数列的第 $i - 1$ 个元素 $n u m s [i - 1]$

当以 $i$ 结尾的序列的上一个元素是数列的第 $j$ 个元素 $n u m s [j]$ 时
以 $i$ 结尾的最长上升序列的的属性 $f [i]$ 应该在 $f [j]$ 的基础上增加1
即 $f [i] = f [j] + 1$

状态转移方程：

$f [i] = ma x (f [i], f [j] + 1)$

最长上升子序列.png

C++代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {

        int n = (int)nums.size(); //

        if (n == 0) return 0;

        vector<int> f(n, 0);
        for (int i = 0; i < n; ++i) 
        {
            f[i] = 1;
            for (int j = 0; j < i; ++j) 
            {
                if (nums[j] < nums[i]) f[i] = max(f[i], f[j] + 1);
            }
        }

        int ans=0;
        for(vector<int>::iterator i=f.begin();i!=f.end();i++) ans=max(ans,*i); 

        return ans;
    }
};

$二分优化 + 贪心 :$

首先，这里存在着一个结论；
不同长度下上升子序列结尾的最小值随着结尾的增大单调递增

这是显然成立的，简单证明一下：
假设存在长度分别为 $i, j$ 属于 $N$ 的上升子序列 $q$ 且在对应长度下结尾元素最小，其中 $j - i = 1$
假如 $q [i] > q [j]$ ，那么就存在一个长度为 $i$ 的且结尾元素是 $q [j]$ 上升序列,与之矛盾

我们可以单独开一个数组 $q$ 作为上升子序列
通过遍历 $n u m s$ 数组来维护 $q$ ，使得 $q$ 数组处于最长上升子序列的状态

遍历数组 $n u m s$ 的过程中
我们可以二分查找出上升子序列 $q$ 中小于 $n u m s [i]$ 的最大的一个元素

若该元素是上升子序列中的最后一个元素，那么该上升子序列长度 $l e n$ 增加，且最后一个元素增加为 $n u m s [i]$
若该元素是上升子序列中的中间某元素，那么就会将该元素替换为 $a [i]$ 。值得注意的是，虽然客观上该上升子序列与实际的最长上升子序列不同，但是替换并不会使得该上升子序列与客观上的最长上升子序列的长度产生差异。

值得注意的是，这里的替换存在着一种特殊情况：当二分查找的结果恰好是子序列中的倒数第二个元素时
我们替换掉的是序列中的最后一个元素
这里蕴含着一个贪心的思想：
对于一个相同长度的字串，当结尾的元素相对较小时，之后可以拓展的机会也就越多，最终获得的上升子序列也就越长

C++代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = 1, n = (int)nums.size();

        if (n == 0) return 0;

        vector<int> q(n + 1, 0);

        q[len] = nums[0];
        for (int i = 1; i < n; ++i) 
        {
            int l=0,r=len;
            while(l < r)
            {
                int mid = l + r +1 >>1;
                if(q[mid] < nums[i]) l = mid;
                else r = mid - 1;
            }

            len = max(len,r+1);
            q[r+1] = nums[i];
        }
        return len;
    }
};

最长公共子序列

原题链接：
洛谷P1439-最长公共子序列

最长公共子序列（Longest Common Subsequence），简称 $L CS$ 。

给定两个序列（可以是字符串也可以是数列）要求这两个字符串中最长的相同子序列
子序列注意区别于子串
子序列不要求两两字符之间连续
若连续可以用KMP算法来求解

状态表示 $f [i] [j]$ (化整为零)
$f [i] [j]$ 表示集合的属性
通过一个二维数组来表示字符串 $a$ 前 $i$ 的位置和字符串 $b$ 的前 $j$ 的位置下出现的子序列

属性：两个字符串公共子序列长度的最大值（max）

状态计算——集合的划分（化零为整）

将集合划分为4个集合
对于集合 $f [i] [j]$ 我们将其同样划分为：

字符串 $a$ 的第 $i$ 个字符和字符串 $b$ 的第 $j$ 个字符均不出现在子序列中
字符串 $a$ 的第 $i$ 个字符包含在子序列中
字符串 $b$ 的第 $j$ 个字符不出现在子序列中
字符串 $b$ 的第 $j$ 个字符包含在子序列中
字符串 $a$ 的第 $i$ 个字符不出现在子序列中
字符串 $a$ 的第 $i$ 个字符和字符串 $b$ 的第 $j$ 个字符不出现在子序列中

当字符串 $a$ 的第 $i$ 个字符和字符串 $b$ 的第 $j$ 个字符均不出现在子序列中
此时的状态应该计算为 $f [i - 1] [j - 1]$

当字符串 $a$ 的第 $i$ 个字符和字符串 $b$ 的第 $j$ 个字符均出现在子序列中
此时的状态应该计算为 $f [i - 1] [j - 1] + 1$

当字符串 $a$ 的第 $i$ 个字符出现在子序列中而字符串 $b$ 的第 $j$ 个字符不出现在子序列时
此时的状态包含在 $f [i] [j - 1]$ 中

$f [i] [j - 1]$ 表示字符串 $a$ 的前 $i$ 个字符和字符串 $b$ 的前 $j - 1$ 个字符组成的子序列
其中包括 $a$ 字符串的第 $i$ 个字符被包含在子序列中和不包含于子序列中
相当于时两种情况的交集

同理：

当字符串 $b$ 的第 $j$ 个字符出现在子序列中而字符串 $a$ 的第 $i$ 个字符不出现在子序列时
此时的状态包含在 $f [i - 1] [j]$ 中

$f [i - 1] [j]$ 表示字符串 $b$ 的前 $j$ 个字符和字符串 $a$ 的前 $i - 1$ 个字符组成的子序列
其中包括 $b$ 字符串的第 $j$ 个字符被包含在子序列中和不包含于子序列中
相当于是两种情况的交集

其中， $f [i - 1] [j - 1]$ 的这种情况被包含在了 $f [i - 1] [j]$ 和 $f [i - 1] [j]$ 两种情况当中

状态转移方程：

$f [i] [j] = ma x (f [i - 1] [j - 1] + 1, f [i - 1] [j], f [i] [j - 1])$

最长公共子序列.png

C++代码暴力朴素算法时间复杂度 $O (n^{2})$

#include<bits/stdc++.h>

using namespace std;

const int N=1010;
int f[N][N];
int a[N],b[N];

int main()
{
    int n;
    scanf("%d",&n);
    
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i] == b[j])
            {
                f[i][j]=max(f[i][j],f[i-1][j-1]+1);
            }
        }
    }
    
    printf("%d",f[n][n]);

    return 0;
}

$离散化 + 二分优化$

我们发现在这个数据中是整数 $[1, n]$ 的全排列，说明每个数字都不会出现重复，每个数字满足唯一性

我们用 $p os$ 数组来存储 $a$ 数组中每个元素的相对位置—数组下标
用 $q$ 数组来维护这个公共子序列

我们将数组 $b$ 中的元素从前到后遍历匹配数组 $a$
如果数组 $b$ 在数组 $a$ 的位置下标 $p os$ 大于维护长度 $q [l e n]$
长度 $l e n$ 增加， $q$ 数组增加元素
反之则将其中的元素替换

#include<bits/stdc++.h>

using namespace std;

const int N=1010;
int a[N],b[N]; //存储a,b两个数列
int pos[N]; //存储a数列中的数字对应的数组下标，也就是出现的顺序
int q[N]; //数组q用来记录数列b相对于数列a的位置下标

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        pos[a[i]]=i;
    }
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    memset(q,-0x3f,sizeof q);
    
    int len = 0;
    q[0]=0;
    for(int i=1;i<=n;i++)
    {
        if(pos[b[i]]>q[len]) q[++len]=pos[b[i]];
        else
        {
            int l = 0, r = len;
            while(l<r)
            {
                int mid = l + r >>1;
                if(q[mid] > pos[b[i]]) r=mid;
                else l = mid + 1;
            }
            
            q[l]=min(pos[b[i]],q[l]);
        }
    }
    
    cout<<len<<endl;

    return 0;
}

区间模型

区间模型的动态规划问题是线性模型动态规划问题的拓展
与其他模型不同，在分阶段划分问题的过程时
不同阶段元素的出现和前一阶段的元素的合并有着很大的关系
即 $f [i] [j] = f [i] [k] + f [k + 1] [j]$

特点

合并性：存在将两个或者多个部分合并为整体的过程
极优性：每个子问题的最优值合并成为最终的最优值

一般方法

区间模型的动态规划问题的方法较为固定
枚举区间的长度 $l e n$ ,在枚举区间的左端点，再根据区间的端点进行状态转移

石子合并

原题链接

洛谷P1880-石子合并

状态表示 $f [i] [j]$ (化整为零)
通过一个二维数组来表示所有将第 $i$ 堆石子到第 $j$ 堆石子合并为一堆石子的合并方式

属性：
$f 1$ 表示所有合并方式得分的最小值 $(min)$
$f 2$ 表示所有合并方式得分的最大值 $(ma x)$

状态计算——集合的划分（化零为整）

将集合划分为 $i - k + 1$ 个集合
对于集合 $f [i] [j]$ 我们将其同样划分为：

以最后一次分界线的位置将集合分为很多类

当分界线在第一堆石子后边时
当分界线在第二堆石子后边时
. . . . . .
当分界线在第 $k$ 堆石子后边时
. . . . . .
当分界线在第 $j - 1$ 堆石子后边时

当分界线在第 $k$ 堆石子后边时
此时将区间 $[l, r]$ 分为 $[l, k]$ 和 $[k + 1, r]$ 两部分
将这两个区间看作为以及合并好的两堆石子
最后合并时的代价是 $f [l] [k] + f [k + 1] [r] + s [r] - s [l - 1] + 1$

状态转移方程：

$f [l] [r] = ma x (f [l] [r], f [l] [k] + f [k + 1] [r] + s [r] - s [l - 1])$

石子合并.png

C++代码

#include<bits/stdc++.h>

#define inf INT_MAX //宏定义无穷大
const int N = 210; //数据范围100

using namespace std;
int a[N],s[N]; //原数组和前缀和数组
int f1[N][N],f2[N][N]; //f1最小得分,f2最大得分
int ans1=inf,ans2=-inf; //ans1存储最小得分,ans2存储最大得分

int main()
{
    int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i+n]=a[i]; //由于石子排列是环形的
	}
	
	for(int i=1;i<=2*n;i++) s[i]=s[i-1]+a[i]; //前缀和初始化要枚举到2n
	
	for(int i=1;i<=n;i++) f1[i][i]=f2[i][i]=0;
	
	for(int len=1;len<n;len++) //枚举区间长度len
	{
		for(int l=1,r=l+len;l<n*2&&r<n*2;l++,r=len+l) //枚举该区间长度len下对应的左端点
		{
			f1[l][r]=inf; 
			for(int k=l;k<r;k++)
			{
				f1[l][r]=min(f1[l][r],f1[l][k]+f1[k+1][r]+s[r]-s[l-1]);
				f2[l][r]=max(f2[l][r],f2[l][k]+f2[k+1][r]+s[r]-s[l-1]);
			}
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		ans1=min(ans1,f1[i][i+n-1]);
		ans2=max(ans2,f2[i][i+n-1]);
	}
	
	cout<<ans1<<endl<<ans2;
	
	return 0;
}

计数类模型

整数问题

原题链接：

AcWing900-整数划分

状态表示
$f [i] [j]$ 表示所有总和是 $i$ 并且恰好表示成 $j$ 个数的和的方案

属性
数量
所有所有总和是 $i$ 并且恰好表示成 $j$ 个数的和的方案的数量 $co u n t$

状态计算
将集合划分为2个部分

集合中的组成和为 $i$ 的整数的 $j$ 个数中最小的数是1
集合中的组成和为 $i$ 的整数的 $j$ 个数中最小的数大于1

对于第一种情况
集合中去掉这一个元素1和集合本身等价
$f [i] [j] = f [i - 1] [j - 1]$

对于第二种情况
集合中方案每一个数都是大于1的
所有我们将这种情况中的每一个数都减去一个1,总和减去 $j$
但是数字的个数不变还是 $j$
所有操作后等价于原集合
$f [i] [j] = f [i - j] [j]$

状态转移方程：
$f [i] [j] = f [i - 1] [j - 1] + f [i - j] [j]$

整数划分.png

#include<bits/stdc++.h>

using namespace std;

const int N=1010,mod=1e9+7;

int f[N][N];


int main()
{
    int n;
    scanf("%d",&n);
    
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            f[i][j]=(f[i-1][j-1]+f[i-j][j])%mod;
        }
    }
    
    int res=0;
    for(int i=1;i<=n;i++) res=(f[n][i]+res)%mod;
    
    cout<<res<<endl;
    
    return 0;
}

这道题有个小trick
可以看成是完全背包问题
每种物品的体积是[1,n]
求解恰好完全装满背包的方式

状态表示
$f [i] [j]$ 表示所有从 $[1, i]$ 中选并且数字之和恰好是 $j$ 的选法的集合

属性
数量
所有从 $[1, i]$ 中选并且数字之和恰好是 $j$ 的选法的集合的数量 $co u n t$

状态计算
将集合划分为 $[0, s]$ 个部分 $s = j / i$

集合中的元素不包含 $i$
集合中的元素含有1个 $i$
集合中的元素含有2个 $i$
......
集合中的元素含有 $k$ 个 $i$
......
集合中的元素含有 $s$ 个 $i$

状态转移方程：
$f [i] [j] = f [i - 1] [j] + f [i - 1] [j - i] + f [i - 2] [j - 2 \times i] + ... + f [i - k] [j - k \times i] + ... + f [i - s] [j - s \times i]$

利用之前的递推性
$f [i] [j - 1] = f [i - 1] [j - 1] + f [i - 1] [j - 2 \times i] + f [i - 2] [j - 3 \times i] + ... + f [i - k] [j - k \times i] + ... + f [i - s] [j - s \times i]$

得出优化后的状态转移方程
$f [i] [j] = f [i - 1] [j] + f [i] [j - 1]$

图我懒得画了

#include<bits/stdc++.h>

using namespace std;

const int N=1010,mod=1e9+7;

int f[N];


int main()
{
    int n;
    scanf("%d",&n);
    
    f[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            f[j]=(f[j]+f[j-i])%mod;
        }
    }
    
    cout<<f[n]<<endl;
    
    return 0;
}

数位统计模型

计数问题

原题链接：

UVA1640-计数问题

求一段区间中每个数字出现的次数
通过转化为函数 $co u n t (n, x)$
表示 $[1, n]$ 中 $x$ 出现的次数

$a - b$ 之间某个数字 $x$ 的个数
可以转化为 $[1, b]$ 之间每个数字出现的次数减去 $[1, (a - 1)]$ 之间每个数字出现的次数
$co u n t (b, x) - co u n t (a - 1, x)$

以 $x = 1$ 为例如何实现 $co u n t$ 函数
$[1, n]$ 之间数字 $1$ 在每个数字的第四位上出现的次数
$n = ab c d e f g$
$1 <= xxx 1 yyy <= ab c d e f g$

分情况讨论：

前三位 $xxx$ 属于 $[000, ab c - 1]$ ,后三位 $yyy$ 属于 $[000, 999]$ —— 一共有 $ab c d \times 1000$ 种选法
前三位 $xxx = ab c$

$d < 1$ , $ab c 1 yyy > ab c 0 e f g$ ——方案数是0
$d = 1$ , $yyy$ 属于 $[000, e f g]$ ——方案数 $e f g + 1$
$d > 1$ , $yyy$ 属于 $[000, 999]$ ——方案数 $1000$

#include<bits/stdc++.h>

using namespace std;

int get(vector<int> nums,int l,int r)
{
    int res=0;
    for(int i=l;i>=r;i--) res=res*10+nums[i]; 
    return res;
}

int power10(int x)
{
    int res=1;
    while(x--) res*=10;
    return res;
}

int count(int n,int x)
{
    vector<int> nums; //存储传入的n的每一位数字注意包含初始化的0
    while(n)
    {
        nums.push_back(n%10); //将数字存入nums
        n/=10;
    }
    
    n = nums.size(); //n此时表示为传入数字的位数即数字的长度
    
    int res=0; //函数的返回值
    for(int i=n-1-!x;i>=0;i--) //i从n-1开始枚举排除初始化的0
    {                          //!x避免前导0的出现
        if(i<n-1)
        {           
            res+=get(nums,n-1,i+1)*power10(i); //第一种分类方式[000,abc-1]
            if(!x) res-=power10(i); //枚举的情况恰好为0时，减去一个power10
        }
        
        if(nums[i]==x) res+=get(nums,i-1,0)+1; //剩余两种情况
        else if(nums[i]>x) res+=power10(i);
    }
    
    return res;
}

int main()
{
    int a,b;
    
    while(cin>>a>>b,a) //读入数字a为0时表示为非结束程序
    {
        if(a>b) swap(a,b); //出现大小顺序a>b时交换数字
        
        for(int i=0;i<=9;i++) //分别输出[a,b]区间中数字0-9出现的次数
        {
            cout<<count(b,i)-count(a-1,i)<<' ';
        }
        
        cout<<endl;
    }
    
    return 0;
}

状态压缩模型

原题链接：
洛谷P1879-Corn Fields

我们分行来处理，每一行进行状态压缩，种草则为 1，不种草则为 0。题目有限制条件，所以我们要筛选有效状态，筛选方法见代码。所以我们在数组的下标中用 $i$ 表示“第 $i$ 个有效状态”。

而每一行的决策只与上一行的状态有关，所以我们设计的状态为——用 $f [i] [j]$ 表示第 $i$ 行状态为 $j$ 的方案数。转移时注意判断与上一行状态的搭配是否合法。

但是我们还要判断这块土地是否贫瘠，有个小 trick：我们把这块土地贫瘠用 1 表示，反之用 0 表示，同样进行状态压缩，如果当前行土地选择状态按位与土地贫瘠状态的结果大于0，则这个方案不合法。

C++代码

#include<iostream>
using namespace std;
const int mod = 1e8;
int m, n, cnt;
const int maxn = 14;
int field[maxn], a[1 << maxn];
int f[maxn][1 << maxn];

int main()
{
    cin >> m >> n;
    for(int i = 0; i < (1 << n); i++)
        if((i & (i << 1)) == 0)  //判断是否有相邻且同时选择的土地
            a[++cnt] = i; 
    for(int i = 1; i <= m; i++)
    {
        int x = 0;
        for(int j = 1; j <= n; j++)
        {
            int val;
            cin >> val;
            x = (x << 1) + (val ^ 1);
        }
        field[i] = x;
    }
    for(int i = 1; i <= cnt; i++)
        if((a[i] & field[1]) == 0)  //判断是否有贫瘠的土地被选择了
            f[1][i] = 1;
    for(int i = 2; i <= m; i++)
    {
        for(int j = 1; j <= cnt; j++)
            for(int l = 1; l <= cnt; l++)
                if((a[j] & a[l]) == 0 && (a[j] & field[i]) == 0)
                //判断与上一行的土地有没有相邻的且有没有选贫瘠的土地
                    f[i][j] = (f[i][j] + f[i - 1][l]) % mod;
    }
    int ans = 0;
    for(int i = 1; i <= cnt; i++)
        ans = (ans + f[m][i]) % mod;
    cout << ans << endl;
    return 0;
}

References:

[1]. R.Bellman. Eye of the Hurricane: An Autobiography.
[2].Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest Clifford Stein.Intorduction to Algorithms < Third Edition >
[3].大雪菜. 闫氏DP分析法

动态规划类问题

目录

动态规划的介绍

动态规划的应用场景

动态规划的基本原理

闫式DP分析法

动态规划的经典模型

背包模型

线性模型

区间模型

计数类模型

数位统计模型

状态压缩模型

树形模型

记忆化搜索模型

参考文献

动态规划的介绍

动态规划的应用场景

动态规划方法应用要素

最优子结构

最优子结构性质：

重叠子问题

重叠子问题性质：

动态规划的基本原理

闫式DP分析法

状态表示 f[i][j] (化整为零)

集合

属性

状态计算——集合的划分

优化

动态规划的经典模型

背包模型

0-1背包问题

状态转移方程：

C++代码

为什么可以转化为一维呢？

如何转化为一维呢？

状态转移方程：

C++代码

完全背包问题

状态转移方程：

C++代码

多重背包问题

状态转移方程：

C++ 代码

C++代码

待补充

分组背包问题

状态转移方程：

C++代码

线性模型

数字三角形

状态转移方程：

C++ 代码

最长上升子序列

状态转移方程：

C++代码

C++代码

最长公共子序列

状态转移方程：

C++代码 暴力朴素算法时间复杂度O(n2)

区间模型

特点

一般方法

石子合并

状态转移方程：

C++代码

计数类模型

整数问题

数位统计模型

计数问题

状态压缩模型

C++代码

References:

C++代码暴力朴素算法时间复杂度 $O (n^{2})$