专项突破 | C++动态规划

©一颗斯特拉

Dynamic Programming(DP)

part1 动态规划知识点总结

01基本概念

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

02基本思想与策略

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

03动态规划的算法设计

1：找出最优解的性质，并描述其结构特征
2：递归定义最优值
3：以自底向上的方式计算最优值
4：根据计算最优值时得到的信息构造出最优解

04能采用动态规划求解的问题的一般要具有3个性质

(1)最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
(3) 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

05使用动态规划求解问题，最重要的就是确定动态规划三要素

(1)问题的阶段
(2)每个阶段的状态
(3)从前一个阶段转化到后一个阶段之间的递推关系。

递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。

确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表（有些简单的情况一维表即可），其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解:f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}。

06动态规划的具体步骤

(1)划分状态：：按照问题的时间或空间特征，把状态分为若干个阶段，即划分子问题。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)状态表示：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3)状态转移：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)确定边界：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。^[1]

part2 动态规划经典例题

01台阶问题（基础）

问题：有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法？

【分析】
(1)划分状态：到达n级台阶，必定是从第n-1级或第n-2级台阶走上来的。走完n级台阶这个问题，依赖于走完n-1级台阶和n-2级台阶这两个阶段。
(2)状态表示：用dp[n]表示走完n级台阶的方法数。
(3)状态转移：dp[n]=dp[n-1]+dp[n-2]。
(4)确定边界：终止条件是n=1或者n=2，当n=1时返回1，当n=2时返回2。
【源代码】

#include<iostream>
#include<string.h>

using namespace std;

#define N 20//【易错】

int dp[N];//全局数组,存放决策表

int f(int n) {
    if (n == 1 || n == 2)
        return n;
    dp[n - 1] = f(n - 1);
    dp[n - 2] = f(n - 2);
    dp[n] = dp[n - 1] + dp[n - 2];
    return dp[n];
}

int main()
{
    f(N);
    cout<<f(4);
    return 0;
}

【运行结果】

5

02最短路径问题（基础）

题目：给定一个m行n列的矩阵，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和，如果给定的矩阵如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12。
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0

【分析】
(1)划分状态：对于除起始位置（第一行第一列）的其他位置，要么是从它左边的位置达到，要么是从上边的位置达到。
(2)状态表示：用dp[m][n]来抽象这个问题，dp[i][j]表示的是从第一行第一列到第i+1行第j+1列位置的最短路径和,a[i][j]表示第i+1行第j+1列的值。
(3)状态转移：因为矩阵中有的元素无左边值或上边值，为防止越界，需要分类讨论。

• 当i!=0&&j==0时，dp[i][j]=a[i][j]+dp[i-1][j]。
• 当i==0&&j!=0时，dp[i][j]=a[i][j]+dp[i][j-1]。
• 当i!=0&&j!=0时，dp[i][j]=a[i][j]+min(dp[i-1][j],dp[i][j-1])。

(4)确定边界：

• 当i==0&&j==0时，dp[i][j]=a[i][j]。

【源代码】

#include<iostream>
#include <algorithm>

using namespace std;


int dp[4][4]={};//全局数组,存放决策表


int main() {
    int a[4][4] = {1, 3, 5, 9, 8, 1, 3, 4, 5, 0, 6, 1, 8, 8, 4, 0};//矩阵存储a[i][j]

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (i == 0 && j == 0)
                dp[i][j] = a[i][j];
            else if (i == 0 && j != 0)
                dp[i][j] = a[i][j] + dp[i][j - 1];
            else if (i != 0 && j == 0)
                dp[i][j] = a[i][j] + dp[i - 1][j];
            else
                dp[i][j] = a[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[3][3];
    return 0;
}

【运行结果】

12

03最大值问题

---

1. 这部分参考了以下文章。
   版权声明：本文为CSDN博主「MISAYAONE」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/misayaaaaa/article/details/71794620 ↩