算法手札：动态规划

Time：2021-5-9

前言

手札，是亲手写的书信，我写的这里自然没有这个意思，只是凑个名字比较好听，嘿嘿。

突然开始学习算法。一切都是从LeetCode的一道题说起(题名：解码方法)，使用递归无论如何优化最终都是超过限制时间，一直无法通过，一看官方答案：“动态规划”，很好，是我没见过的东西，于是就开始了算法的学习(流下了菜鸡的泪水)。看了一晚上的背包问题，最终得出结论：算法什么的是学不会的了。现在越学越觉得要好好考虑是否要准备转计算机，还是继续混电气好qwq。

以下编程均使用C++来实现。

文章前面记录动态规划算法的一些理论描述，后面记录题目与我的解题思路，为的是可以在日后需要再次复习时可以快速重新学一次和回想起来。

转载请注明出处！！！

Author：雾雨霜星

欢迎来我的个人网站进行学习：

https://www.shuangxing.top/#/passage?id=21

动态规划算法

概念：

我的理解是：

把一个问题分按照多个阶段分为多个子问题，通过求解并记录子问题的解，结合前面所得的子问题的解最终得到原问题的解。

每个子问题是整个问题中的一个阶段，往往与前面状态的子问题有关，他们之间的关系就是状态转移方程。

子问题与原问题是相似的，只是子问题所需要考虑的对象只有一部分。

采用记忆化搜索，记录子问题的解，不对子问题做重复解答。

进一步描述，就是对于一个事件A，分解为许多小事件Ai(i=1,2,3…)，而An的状态可以由所有前面的子事件的状态Ak(k=1,2,3…,n-1)决定。从Ak(k=1,2,3…,n-1)得到An的方法就是状态转移方程，而根据所有的事件状态可以得到事件A的状态。

与其说是算法，这更加像是一种解题方法。

一般的做法：
1. 确定问题的边界条件。即在某种特殊状况下可以直接得到问题的解。
2. 把原问题划分为子问题。对于原问题，其过程必然是由一些列重复的子过程组合而成的，每个子过程的执行结果都可以由在前面所有的子过程执行的结果来决定。
3. 确定状态转移方程。即每个子问题如何根据之前所有执行的结果来进行解决。

背包问题

问题描述如下：

背包问题: 
在N件物品中取出若干件放在容量为W的背包里。每件物品的体积为w1,w2……,wn（wi 均为整数），各物块相对应的价值为p1,p2……,pn（pi为整数），求背包能够容纳的最大价值。

动态规划算法的思路：

问题分析：

问题中描述了一个事件：把若干物块放入到背包，有很多种组合方法，最终背包中所有物块价值总和为最大。这个事件的过程就是放入物块组成的，对于每个物块，考虑放入与不放入，最终全部考虑完毕，得到背包容纳最大价值。

如果这些wi与pi都给定，那就存在某种组合使得背包可以容纳最大价值。但是我们不需要给出这个组合，只需给出最大价值。

算法过程：

确定边界条件：没有明确的可以直接确定解的状况(不考虑全部物块体积为0和全部物块体积都比背包体积大)。
确定子事件：对于物块1,2,3…,i，在背包体积上限为j的状况下，背包的最大容纳价值。 (0≤i≤N,0≤j≤W)
确定状态转移方程：

如果在背包体积为j-wi下背包容纳的最大的价值与pi的和比背包体积为j时最大的价值更大，那就放入，否则不放入。

包体积为j时考虑第i个物块的最大价值 = max{ 包上限为j时考虑第i-1个物块的最大价值, 包上限为j-wi时考虑第i-1个物块的最大价值 + pi}

为什么是这样的，因为如果第i个物块要放进去，那么背包j>wi而且在j-wi时放入其余物块到背包有最大价值。

//定义二维数组dp[i][j],表示背包体积为j时,考虑1,2,3…,i物块时最大容纳价值

//状态转移方程:

dp[i][j]=max{dp[i-1][j],dp[i-1][j=w[i]]+p[i]}

4. 分析：

假如已经知道最终通过组合物块k1,k2,k3...,kn可以得到背包容纳最大价值。那么在背包体积为W-kn时，不考虑物块kn，背包最大容纳价值的方法是k1,k2,k3...,kn-1组合。同理，在在背包体积为W-kn-kn-1时,不考虑物块kn与kn-1，背包最大容纳价值的方法是k1,k2,k3...,kn-2组合......

但是，我们无需给出组合方法，只需要知道，在背包体积为W，考虑放入与不放入物块kn可以得到最大背包容纳价值，如果放入，意味着背包空间最多只使用 了W-Kn，此时可以放入kn，放入之后的价值是：背包体积使用到最多W-kn时的价值+kn物块的价值，而为了寻找最大的价值，所以应该是：背包体积使用到最多W-kn时的最大容纳价值+kn的价值。同时比较，当不放入物块kn，即背包体积考虑了物块1,2,3...n-1后使用最大体积为W时的容纳的价值。同理，背包体积使用到最多W-kn时的最大容纳价值，是比较了kn-1后的最大容纳价值，即：背包上限为W-kn-kn-1时不考虑kn与kn-1背包容纳的最大价值与kn-1价值之和，与，背包上限为W-kn时不考虑kn与kn-1背包容纳的最大价值，之间比较得到的较大值。

可见，给出：1.背包体积上限为 j，考虑了i-1个物块时的最大容纳价值。与，2.背包体积上限为 j-wi，考虑了i-1个物块时的最大容纳价值。再由第i个物块的价值vi，就可以得到背包体积上限为 j，考虑了i个物块时的最大容纳价值。那么一直推导，到最后就可以确定，背包体积上限为 W，考虑了N个物块时的最大容纳价值。

所以，如果可以确定每个状态下背包的最大价值，那么就可以确定背包的最终最大价值。

从上面的分析也看出了，子问题是：在考虑了i个物块后，背包体积上限为j时的最大容纳价值。

按照为了得到每个子问题的解，最大容纳价值，可以确定状态转移方程：dp[i][j]=max{dp[i-1][j],dp[i-1][j=w[i]]+p[i]}。

而我们最终的分解是：

事件A(W, N)：背包体积为W且考虑物块N后最大容纳价值。分解为，一系列事件A(i , j)：背包体积为 j且考虑物块 i后最大容纳价值。

与我上述动态规划算法的理解中的说法一致。

解答方法：

public static int PackageSolution(int w[],int p[],int PackageVolume){//w[]每个元素均为整数，p[]每个元素均为整数，PackageVolume是非0整数
    int const BlockNum = sizeof(w)/4; //确定物块数量; int占4字节
    //定义用于存储每个子问题的解的数组
    int **dp;
    dp = new int*[BlockNum+1];
    for(int i=0;i<=BlockNum;i++)dp[i] = new int[PackageVolume+1];
    for(int i=0;i<=BlockNum;i++){
        for(int j=0;j<=PackageVolume;j++){
                dp[i][j]=0;
        }
    }
    for(int i=1;i<=BlockNum;i++){
        for(int j=1;j<=PackageVolume;j++){
            if(j>=w[i]){
                /*
                放入物块，则得到背包价值：考虑了i-1个物块后背包体积上限为j-w[i]的最大容纳价值 + 物块i价值p[i]
                不放入物块，则得到背包价值：考虑了i-1个物块后背包体积上限为j的最大容纳价值
                dp[i][j]:考虑了i个物块后背包体积上限为j的最大容纳价值
                */
                dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+p[i]);
            }
           else{
               //由于放不下物块，与不放入物块的最大容纳价值相同。
               dp[i][j]=dp[i-1][j]; 
           }
        }
    }
    return dp[BlockNum][PackageVolume];
}

因为动态规划算法核心思想是减少重复计算，需要采用记忆化搜索，所以每次子问题的解都要记录下来。

考虑到对体积处理，采用所有上限均考虑的方法。

如下，使用滚动数组，即创建一维数组解决背包问题。

public static int PackageSolution(int w[],int p[],int PackageVolume) {
		//设置一个二维数组，横坐标代表从第一个物品开始放到第几个物品，纵坐标代表背包还有多少容量，dp代表最大价值
        int const BlockNum = sizeof(w)/4;
		int dp[] = new int[PackageVolume+1];
		for(int i=1;i<=BlockNum;i++){
            //dp[i][j]的值只与dp[i-1][0,...,j-1]有关，因此上一次的dp[j+1,...,PackageVolume]都可以放弃
            //j 要逆向递减(逆向枚举)，防止上一层循环的dp[0,...,j-1]被覆盖
			for(int j=PackageVolume;j>0;j--){
				if(j>w[i]){
					dp[j] = Math.max(dp[j], dp[j-w[i]]+p[i]);
				}else{
					dp[j] = dp[j];
				}
			}
		}
		return dp[PackageVolume];

对于背包问题，采用暴力枚举，无疑需要大量的重复计算和判断。

第i件物品装入或者不装入而获得的最大价值完全可以由前面i-1件物品的最大价值决定，暴力枚举忽略了这个事实。

动态规划之背包问题系列:https://tangshusen.me/2019/11/24/knapsack-problem/

解码方法

问题描述如下：

一条包含字母 A-Z 的消息通过以下映射进行了 编码:
'A' -> 1
'B' -> 2
...
'Z' -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
"AAJF" ，将消息分组为 (1 1 10 6); "KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways

动态规划算法思路：

算法过程：
1. 确定边界条件：
  
  如果s第一个字符是0，则无解码方法。即：if(s[0]==‘0’)return 0;
2. 确定子问题：
  
  s[0,…,i]的字符串的解码方法数量。
3. 确定状态转移方程：
  
  s[0,…,i-1]共有N1种解码方法。s[0,…,i-2]共有N2种解码方法。
  
  只考虑把s[i]作为一个字符解码，则s[0,…,i]共有N1种解码方法。
  
  只考虑把s[i-1]s[i]合并作为一个字符，则s[0,…,i]共有N2种解法。(s[i-1]==1 || (s[i-1]==2&&s[i]<=6))。
  
  若上述两个均成立，则s[0,…,i]共有N1+N1种解法。
  
  对于s[i+1]=='0’的状况，只允许s[i]解码为一个字符，不可以考虑把s[i-1]s[i]合并作为一个字符。
4. 分析：
  
  输入字符串如果第一个字符为0，或者中间存在前面字符不是1或2的0字符，那么就没有解码方法。
  
  如果采用递归，本质其实就是暴力枚举，因为每检查到一个字符，就需要把后面所有字符检查一次，所以相当于重复检查了很多次。
  
  我感觉，就我个人而言，要直接看出这道题目使用动态规划，需要自己做过很多题，知道这一类的固定的组合的题目，适合使用动态规划算法，否则，如果不能及时意识到：i长度的字符串的解码方法可以由i+1长度的字符串的解码方法确定，那么就很难想到动态规划了。

解答方法：

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        if(s[0]=='0')return 0;
        if(n==1)return 1;
        int* dp=new int[n];
        dp[0]=1;
        for(int i=1;i<n;i++){
            if(s[i]=='0'){
                if(s[i-1]=='1'||s[i-1]=='2')dp[i]=dp[i-1];
                else return 0;
            }
            else{
                if(s[i-1]=='1' || (s[i-1]=='2'&&s[i]<='6')){
                    if(i<n-1&&s[i+1]=='0')dp[i]=dp[i-1];
                    else if(i>1)dp[i]=dp[i-1]+dp[i-2];
                    else dp[i]=dp[i-1]+1;
                }
                else dp[i]=dp[i-1];
            }
        }
        return dp[n-1];
    }
};

错误思路：

我采用的是递归方法，即一个函数f(s,i)，每次检查s[i]，根据s[i]的状况来进行if else分开讨论。设置一个变量a用于统计方法数，如果i+1存在就会递归去检查s[i+1]。

会出现超出时间限制的状况。源代码未保留可惜了。

零钱兑换

问题描述如下:

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
数据类型：coins是整形数组，amount是整形数字。(coins[i]>0,amount>=0)

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change

动态规划算法步骤：

子问题：在不同金额下考虑的兑换最小数。
边界条件：amount==0或者coins的长度为1。
解答方法：
```
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < (int)coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/
来源：力扣（LeetCode）
           
```
使用一个循环迭代每种可能出现的余额amount，然后在每种可能出现的余额dp[i]中迭代每种面额，讨论每种面额是否放入。这里巧妙的是不需要但单独通过循环来寻找每种面额放入的数量，而是在每次余额的叠加中进行面额的循环，每次讨论是否放入某种面额coins[j]时，回溯到可以放入该面额的余额的状态dp[i - coins[j]]中的时候，前面的最小数量可能已经包括了这个面额。这样就可以记录每种余额状态下的最小兑换数了。

这个解答思路很聪明，初始化所有元素为amount+1，把dp[0]设置为0，方便后面的比较以及迭代到相应余额的时候知道是否已经讨论过了。

我的思路的问题：

我也采用了动态归还算法，但是我的做法却超出了时间限制。代码如下：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount==0)return 0;
        int const num = coins.size();
        if(num==1){
            if(amount%coins[0]==0){
                return amount/coins[0];
            } 
            else return -1;
        }
        int **dp;
        dp = new int*[num+1];
        for(int i=0;i<=num;i++)dp[i] = new int[amount+1];
        for(int i=0;i<=num;i++){
            for(int j=0;j<=amount;j++){
                dp[i][j]=0;
            }
        }
        for(int i=1;i<=num;i++){
            for(int j=1;j<=amount;j++){
                if(j>=coins[i-1]){
                    int x = j/coins[i-1];
                    int temp=0;//用于寻找在判断是否放入某种面额时，放入该指定面额不同数量下的最小的兑换数
                    for(int n=1;n<=x;n++){
                        //首先考虑是否可行
                        if(dp[i-1][j-n*coins[i-1]]==0){
                            if(j-n*coins[i-1]==0){ //对于给定j,复合此条件，那么其他n的时候必然不成立
                                if(temp==0 || n<temp)temp=n;
                                else continue;
                            }
                            else continue;
                        }
                        else if(temp==0 || dp[i-1][j-n*coins[i-1]]+n<temp)temp=dp[i-1][j-n*coins[i-1]]+n;
                        else continue;
                    }
                    if(dp[i-1][j]==0)dp[i][j]=temp;
                    else if(temp!=0 && temp<dp[i-1][j])dp[i][j]=temp;
                    else dp[i][j]=dp[i-1][j];
                }
                else dp[i][j]=dp[i-1][j];
            }
        }
        if(dp[num][amount]==0)return -1;
        else return dp[num][amount];
    }
};

存在这样的几个问题。

首先是关于初始化。我对数组中每个元素的初始化是0，即代表在余额为j，只考虑使用前面i种面额的最小数量为0。这样初始化在执行

dp[i-1][j-n*coins[i-1]]+n

的时候会比较方便，但是对于判断这个方法到底是0还是无解，是未经讨论还是讨论后无解，带来多种可能，因此需要额外大量的if语句。

然后是采用了对每种面额使用多少，进行具体讨论，即我的代码中的n循环语句，在这个以int x = j/coins[i-1];为极限的for循环语句中，寻找使用该面额不同数量的时候最小的兑换数，存放到temp变量中，与不使用该面额的状况进行比较。这里重复计算的部分就是，寻找使用某种面额的数量，这个部分的确定，完全是多余的。

我忽略了一个重要的事实：在子问题解中，讨论面额coins[i]的时候，coins[i]可能已经使用了。

我相当于把前面是否使用这个面额再讨论了一次。

总结

题目特点：
- 最终的解存在最优的子结构解
- 带有限制条件的固定组合方式
只要题目是存在这样的特点，都可以优先考虑使用使用动态规划进行处理。

通过寻找最佳子结构解，可以确定子问题，从而确定递推关系。
处理过程避免重复计算：

主要是，往往题目不会要求给出具体的解的结构，因此在迭代过程中可以忽略具体使用了哪一个进行组合。

比如：背包问题，不需要具体知道放入物块的W；解码方法，不需要只带当前具体是如何划分来组合；零钱兑换，不需要具体知道使用面额。

因此，在迭代过程中，对限制条件是通过+1的方法（步长为1）来子问题的解，只需要知道当前是否符合条件，与之前进行比较，满足最优即可。

比如：背包问题，背包空间每次+1，部分物块下，比较当前物块是否可以放入，若可，则比较放入后与不放之间哪个更好；零钱兑换，每次余额+1，所有面额下，比较当前面额是否可以使用，若可，则比较使用与不使用哪个更加好。

区分上述的背包问题与零钱兑换，一个中重要的区别：背包问题中物块每次只可以放一个；零钱兑换中每种面额可以放多个。这种差异也造就了两者寻找子问题解的方法不一样，背包问题：每种物块在各种体积下是否放入一个；零钱兑换：每次余额增加下讨论各种面额是否使用。

两者上述寻找子问题解的过程的区别，对应的也是子问题解的结构区别：背包问题，对于最优解，在放入最后一个物块之前，不考虑那个物块与那部分体积下已经有最大价值。零钱兑换，在使用最后一个硬币时，不考虑余下的额度，考虑所有面额的纸币，已经有最小兑换数。

总而言之，如下：
- 采用记忆化搜索，设置数组保存每个子问题的解。
- 不讨论具体的实现方案。
子问题求解过程：

如果限制每种内容组合只使用一次，迭代组合的内容，每种组合内容物体都迭代一次限制条件，每次限制条件步长增加(常用+1)。

如果限制每种内容组合可以使用多次，迭代限制条件，每次限制条件步长增加(常用+1)，迭代组合的内容。

转载请注明出处！！！

Author：雾雨霜星

欢迎来我的个人网站进行学习：

https://www.shuangxing.top/#/passage?id=21

Thanks！

PS: 毕竟，霜星酱水平有限，如果发现任何错误还请及时邮箱告知我，我会去改哦！

算法手札：动态规划算法手札：动态规划

算法手札：动态规划

动态规划算法

背包问题

解码方法

零钱兑换

总结

继续阅读

[转]ISUP信令的IAM消息详细内容

swmm与lisflood-fp源码如何一起编译 CMake命令

Windows下VS开发环境环境安装工程项目设置关于Debug和Release的提示

一文看懂字符串的加减乘除

C++ 第十五周报告1--《冒泡法排序》

HDU 1160 FatMouse's Speed （记录路径的最长上升子序列）

C++实现简单顺序表

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

C经典书籍笔记——C陷阱与缺陷②(语法陷阱之优先级)一、错误案列二、优先级规律

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

线性表之顺序表的实现

C++判断素数、求最大公约数代码判断一个数是否为素数求两个数的最大公约数

SequoiaDB巨杉数据库C++驱动概述

Linux设备模型（中）之上层容器