动态规划(dp)入门

动态规划入门

一，动态规划的关键概念

1.重叠子问题

动态规划是将一个多阶段问题分成几个相互联系的单阶段问题。这几个相互联系的单阶段问题一定要是同类型的子问题，这样分成多阶段决策才有意义，否则每次面对的都是不同的问题，也就失去了分成单阶段的意义。在《算法导论》中，把这种同类型的子问题叫做”重叠子问题“。重叠不是完全相同，而是同类型，可以通过解决子问题，然后合并子问题的解而得到原问题的解。

动态规划中子问题的“重叠”，体现为可以用一个多项式来表示每个子问题。利用子问题的初始解和递推多项式，可以求出每个子问题的解，最终求出整个问题的解。

2.最优子结构

用动态规划求解最优化问题的必要条件是描述最优解的结构。如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。动态规划用于求解最优化问题，且问题的最优解中包括了子问题的最优解，所以具有“最优子结构”。

当一个问题具有最优子结构时，提示我们动态规划可能会适用。动态规划以自底向上的方式来利用最优子结构，首先找到子问题的最优解，解决子问题，然后找到问题的一个最优解。也就是说，求解小问题，然后推出大问题的解。

3.无后效性

无后效性又称为马尔可夫性（Markov property），是一个概率论中的概念。无后效性是指如果给定某一阶段的状态，则此阶段以后过程的发展仅与此阶段的状态有关，而不受此阶段以前各阶段状态的影响。通常浓缩成一句简短的“未来与过去无关”。问题的历史状态不影响未来的发展，只能通过当前的状态去影响未来，当前的状态是以往历史的一个总结。

在利用动态规划方法求解多阶段决策问题时，过程的状态必须具有无后效性。具体地说，如果k阶段的值已经确定，则在k+1阶段只关心k阶段的值，而不用关心k阶段的值是怎么求出来的，也不用关心k阶段以前的阶段的值。

4.状态描述和初始状态

在使用动态规划解决问题时，要能正确地描述最优解的结构，对最优解的结构进行准确描述称为“状态描述”。状态描述确定后，可以根据描述找到子问题的初始值（边界值），也即初始状态，问题的最终解将依据初始状态逐步推导得出。

状态描述对解决问题至关重要，且它并没有看起来那么简单，在解决千变万化的实际问题时，经常需要复杂的分析才能构造出最优解的结构。因为对最优化问题的状态描述需要满足最优子结构和无后效性，才能满足用动态规划解决问题的前提。

5.状态转移

动态规划将问题分解成多个阶段的子问题，并定义了每一个阶段的状态描述，在问题求解过程中，每个状态均可以由前序的状态推导得出，这种由前序状态推导出当前阶段状态的过程称为状态转移。

如果要利用前序阶段子问题的结果解决现阶段的子问题，必须要能够建立前后阶段状态的转移关系。状态转移的转移方式通常可以用问题规模的多项式来表示，描述状态转移的多项式称为状态转移方程，也可以称为递推公式。状态转移方程确定了由一个状态到另一个状态的演变过程，列出状态转移方程也是求解动态规划问题中的一个关键点和难点。

二，动态规划的一般求解步骤

动态规划问题的核心步骤有定义问题的状态、列出状态转移方程、状态初始化和代码求解。

1.定义问题的状态

定义问题的状态是要明确状态表示什么含义，定义的状态需要满足最优子结构和无后效性，如果问题的状态定义得不对，会导致无法用动态规划来求解。

具体到代码中，就是要定义 dp 数组中每个元素的含义，以及 dp 数组中下标的含义。代码中一般都会用一个数组来存储所有子问题状态的值，这个数组可以是一维数组 dp[i] 或二维数组 dp[i] [j]等。明确状态的含义是列出状态转移方程和问题求解的前提。

2.列出状态转移方程

状态转移方程是指从前序状态推导出当前状态的推导关系，通常可以用问题规模的多项式来表示，所以也常称为递推公式。列出正确的状态转移方程，是动态规划问题中非常重要的一个步骤，也是一个比较困难的步骤。

具体到代码中，就是找到 dp[i] 与 dp[i-1]，dp[i-2], … 的关系，用 dp[i-1]，dp[i-2], … 来表示 dp[i] 。例如，用 dp[i] 表示 i 的阶乘，则 dp[i] = i * dp[i-1]，用 dp[i] 表示斐波那契数列，则 dp[i] = dp[i-1] + dp[i-2] 。递推公式在不同问题中是千变万化的，所以要分析清楚问题，从定义状态时就开始考虑递推公式的推导，假如无法得到递推公式，可以重新分析问题的状态定义得是否适合。

3.状态初始化

在定义完状态和找到递推公式后，需要求解问题的初始值，才能有递推解决问题的起点。动态规划的每一个状态都是从前序状态推导而来的，所以一定有初始值，也就是状态转移的起点。不过，起始状态并不是一成不变的，要根据定义的状态，找到有意义的初始值。

具体到代码中，求初始值就是求出起始状态的值。例如，阶乘的初始值是 dp[1] = 1，斐波那契数列的初始值是 dp[1] = 1, dp[2] = 1。在具体问题中，有些问题的初始值是从下标 1 开始，有些问题的初始值是从下标 0 开始，还有些问题的初始值是从 n-1 开始，等等。有些问题需要一个初始值，有些问题需要多个初始值。所以在求初始值时要根据状态定义和递推公式来调整，具体问题具体分析。

4.代码求解

前面的三个步骤主要是对问题进行剖析，找到解决问题的方法。

完成前面的步骤后，我们需要根据思路编写代码、运行代码得到结果。相对于前面三步而言，编写代码其实是最简单的一步，动态规划的代码通常像套公式一样，因为只要经过了前面的分析，写代码只是把结果计算出来。虽然说，不编写代码并执行，就得不到结果，但是在动态规划中，关键在于解题思路，很多人甚至没有把编写代码当成一个步骤。

三，刷题完事

线性DP：

上楼梯 数字三角形

最长上升子序列 接龙数列

背包问题:

01背包问题 拼题A打卡奖励

完全背包问题 整数拆分 硬币问题

区间DP:

石子合并（弱化版)

数位DP:

windy 数 相邻差值

树形DP:

没有上司的舞会
状态压缩DP
单调队列优化DP
斜率优化DP

……

四，模板题

上楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
const int N = 100;
// 状态表示：dp[i] 表示到达第i层阶梯的方案数
// 状态转移： dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
// 初始值： dp[1] = 1; dp[2] = 2; dp[3] = 4;
int dp[N];
int main()
{
	int n; cin >> n;
    dp[1] = 1; dp[2] = 2; dp[3] = 4;
	for(int i = 4; i <= n; i++)
		dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
	cout << dp[n] << endl;
	return 0;
}

最长上升子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
// 状态表示：dp[i]表示以第i个数字为结尾的最长上升子序列长度
// 状态转移：if(f[i] > f[j]) dp[i] = max(dp[i], dp[j] + 1);  
// 初始值： for(int i = 1; i <= n; i++) dp[i] = 1;
int dp[N], f[N];
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> f[i];
    int res = 1;
    for(int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        for(int j = i - 1; j >= 1; j--)
            if(f[i] > f[j])
                dp[i] = max(dp[i], dp[j] + 1);
        res = max(res, dp[i]);
    }
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 单调栈优化
#include<iostream>
#include<vector>
using namespace std;
const int N=100010;
int f[N];
int main()
{
    int n; cin>>n;
    vector<int> v;
    for(int i = 1;i <= n; i++)
        cin >> f[i];
    v.push_back(f[1]);
    for(int i = 1;i <= n; i++)
    {
        if(f[i] > v.back()) v.push_back(f[i]);
        else *lower_bound(v.begin(),v.end(),f[i]) = f[i];
    }
    cout<< v.size() << endl;
    return 0;
}

数字三角形 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int dp[N][N];
// 状态表示：dp[i][j]表示从顶点到达(i, j)这个点的最大路径和
// 状态转移：dp[i][j] += max(dp[i-1][j], dp[i-1][j-1]);
// 初始值： dp[1][1] = f[1][1]; 
int main()
{
    int n; cin >> n;
    memset(dp, -0x3f, sizeof dp);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
        {
            cin >> dp[i][j];
            if(i != 1 || j != 1)
                dp[i][j] += max(dp[i-1][j], dp[i-1][j-1]);
        }
    int res = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++)
        res = max(res, dp[n][i]);
    cout << res << endl;
    
    return 0;
}

01背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream> 
using namespace std; 
const int N = 1010; 
// 状态表示：dp[i][j]只有前i个物品且背包容积为j时的最大价值 
// 状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
// 初始值：for(int i = 0; i <= n; i++)
//        	dp[i][0] = 0, dp[0][i] = 0; (没有物品时和背包容积为0时，价值为0)
int dp[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 = 1; j <= m; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
        }
    cout << dp[n][m] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 滚动数组优化(一个数组重复利用)
#include <iostream> 
using namespace std; 
const int N = 1010; 
int dp[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 = v[i]; j <= m; j++)
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
            
    cout << dp[m] << endl;
    return 0;
}

完全背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream> 
using namespace std; 
const int N = 1010; 
// 状态表示：dp[i][j] 表示使用前i个物品, 背包容积为j时, 能得到的最大价值
// 状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i], dp[i-1][j-2*v[i]) + 2*w[i]...); 
// 初始值：for(int i = 0; i <= n; i++)
//        	dp[i][0] = 0, dp[0][i] = 0; (没有物品时和背包容积为0时，价值为0)
int dp[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 = 1; j <= m; j++)
            for(int k = 0; j/v[i] >= k; k++)
                dp[i][j] = max(dp[i][j], dp[i-1][j - v[i] * k] + w[i] * k);
                
    cout << dp[n][m] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 状态表示：dp[i][j] 表示使用前i个物品, 背包容积为j时, 能得到的最大价值
// 状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i], dp[i-1][j-2*v[i]) + 2*w[i]...); 
// 初始值：for(int i = 0; i <= n; i++)
//        	dp[i][0] = 0, dp[0][i] = 0; (没有物品时和背包容积为0时，价值为0)

// dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i], dp[i-1][j-2*v[i]) + 2*w[i] );
// dp[i][j-v[i]]  = max(dp[i-1][j-v[i]], dp[i-1][j-2 * v[i]] + w[i], dp[i-1][j-3 *v[i]) + 2*w[i] );
// dp[i][j] = max(dp[i-1][j],  dp[i][j-v[i]] + w[i]);
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std; 
const int N = 1010;
int n, m;
int v[N], w[N], dp[N][N];
int main()
{
    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 = 1; j <= m; j++) 
        {
            dp[j] = dp[j];
            if(j >= v[i])
                dp[i][j] = max(dp[i-1][j],  dp[i][j-v[i]] + w[i]);
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

石子合并（弱化版)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int dp[N][N];
int n, f[N];
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> f[i];
        f[i] += f[i-1];
    }
    memset(dp, 0x3f, sizeof dp);
    for(int i = 1; i <= n; i++)
        dp[i][i] = 0;
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; i+j-1 <= n; j++)
        {
            int l = j, r = i + j - 1;
            for(int k = j + 1; k <= r; k++)
                dp[l][r] = min(dp[l][k-1] + dp[k][r] + f[r] - f[l-1], dp[l][r]);
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

五，练习题

接龙数列 拼题A打卡奖励

整数拆分 硬币问题

奇怪的汉诺塔

装箱问题

分割等和子集

股票买卖 IV

接龙数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
using namespace std;
const int N = 100010;
int f[N], dp[N];
int main()
{
    int n; cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> f[i];
        int l = f[i]%10;
        while(f[i] >= 10) f[i] /= 10;
        f[i] = f[i] * 10 + l;
    }
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for(int j = i-1; j >= 0; j--)
        {
            if(f[i]/10 == f[j]%10)
                dp[i] = max(dp[j] + 1, dp[i]);
        }
        res = max(res, dp[i]);
    }
    cout << n - res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
using namespace std;
const int N = 100010;
int f[N], dp[N][20];
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> f[i];
        int t = f[i]%10;
        while(f[i] >= 10) f[i] /= 10;
        f[i] = f[i] * 10 + t;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= 9; j++)
            dp[i][j] = dp[i-1][j];

        dp[i][f[i]%10] = max(dp[i][f[i]%10], dp[i-1][f[i]/10] + 1);
    }
    int res = 1;
    for(int i = 0; i <= 9; i++)
        res = max(res, dp[n][i]);
        
    cout << n - res << endl;
    return 0;
}

拼题A打卡奖励

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 背包解法 TLE
#include <iostream>
using namespace std;
const int N = 1010;
int v[N], w[N], dp[N][N];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> v[i];
    for(int i = 1; i <= n; i++)
        cin >> w[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= v[i])
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i]);
        }
    cout << dp[n][m] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
//dp[i][j] 表示前i个物品，得到j枚金币，花费的最小时间 
int v[N], w[N], dp[N][30*N];
int main()
{
    int n, m;
    cin >> n >> m; 
    for(int i = 1; i <= n; i++)
        cin >> v[i]; 
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i];
        sum += w[i];
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= sum; j++)
        {
            dp[i][j] = dp[i-1][j]; 
            if(j >= w[i])
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
        }
    int t = sum;
    while(dp[n][t] > m) t--;
    cout << t << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 优化空间
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010; 
//dp[i][j] 表示前i个物品，得到j枚金币，花费的最小时间 
int v[N], w[N], dp[30*N];
int main()
{
    int n, m;
    cin >> n >> m; 
    for(int i = 1; i <= n; i++)
        cin >> v[i]; 
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i]; 
        sum += w[i]; 
    }
    memset(dp, 0x3f, sizeof dp); 
    dp[0] = 0; 
    for(int i = 1; i <= n; i++)
        for(int j = sum; j >= w[i]; j--)
                dp[j] = min(dp[j], dp[j-w[i]] + v[i]); 
    int t = sum;
    while(dp[t] > m) t--;
    cout << t << endl;
    return 0;
}
算法刷题 > 算法学习
#算法竞赛 #dp #动态规划
动态规划(dp)入门
https://leaf-domain.gitee.io/2024/01/14/dp/
作者
叶域
发布于
2024年1月14日
许可协议