【算法】动态规划问题的常见解决办法

vlambda
2020-02-20

【算法】动态规划问题的常见解决办法

做这个的起因是我一开始觉得动态规划问题的题解都长得好相似啊，然后再研究了紫书，感觉这个可以总结一下，有些人给的是挨个推的讲解，我觉得他们讲的很好，但是有点停留了，我的目的是把整个推演的表示给提炼出来，废话不说了开始吧。

零、引言

动态规划问题是一种常见的算法比赛问题，极为经典也较为困难，原因是大多数题目类似于递归问题，但是如果真的用递归去解决的话会出现诸如超时等丢分问题，为此，动态规划问题的常用解决办法便诞生了，开门见山，直接列方法：

一、思想框架

思想：用空间换取时间。

首先我们不看动态规划方法，而是先去了解递归方法，递归方法的逻辑很简单“解决父问题就要先解决子问题，解决子问题就要解决孙问题......”但是当存在两个以上的子问题的时候，可能会出现调用同一个孙问题的情况，这样就会无端的浪费时间，多重调用，造成浪费，为此，动态规划方法出现了，动态规划方法解决这个时间浪费的方法是：把已经解决了的问题存储下来，每次遇到直接调用就行了，节省了多次重复。

这就是动态规划思想“用空间换时间”的由来。

二、三大步骤

解决这种动态规划问题常用三个步骤

1 >构建状态数组dp，动态规划常用的思想就是状态，当你处在什么状态的时候，对应的数组f[i][j]就存储着该种状态。而且这一步也非常关键，只有能理解了“状态”这个词的概念，才能运用状态转移方程。

2 >状态转移方程，一般形式是数组的形式写出来的，以《数字三角形》[2]为例，该问题的状态转移方程为 dp[i][j] = max/min(dp[i,j]，dp[i + 1, j]+ a[i])

状态转移方程的理解就是：前一个问题dp[i][j]对后一个问题会产生什么影响呢？每一个状态的数学表示可以表示为 z = dp[i][j]有三个参数 z，i，j。这三个参数z代表了这个状态的量值是多少 i一般代表了该状态的序号，j一般代表了该状态的第几个情况。

而影响“状态”数组的有两个，一是前一个状态，没什么好说，递归都是这样。二则是状态转移时候的“代价”，而代价，一般就是我们一开始输入的内容，譬如爬楼梯需要的高度，摘苹果需要的体力等等。

3 >循环构成，因为整个状态数组的构建过程是需要通过一个遍历过程的（i变量的遍历）。而且在这个过程中，每个状态中又有着多种可能（j变量的遍历），所以确定遍历，便是第三个关键点，这三个关键点确定了，便可以确定整个核心算法了。

三、三大要素

代价数组 a[N]//存储每一个代价

状态数组 dp[N][M] //存储每一个状态

状态转移方程 f(dp) //一般表示形式是本状态 = f（本状态 or 前状态 + 代价） f是某一状态的选择方式，比如最小或者最大

四、代码框架

这里只讨论迭代方法：

//C++掺杂文字表示伪代码#include <iostream>using namespace std;
const int N = 12345;const int M = 123;int a[N]; //代价数组int dp[N][M]; //状态数组
int main(){ int n; // 输入n的值 //用for循环输入a数组的值
 //将dp数组初始化为某一特定值 memset(dp, 0x3f, sizeof(dp)); //初始化所有的f动态规划数组为无穷大 for (int i = 0; i < length1; i++) { for (int j = 0; j < length2; j++) { // 可能还有for循环      // 这里是状态转移方程   } } // 一般情况是这样的一个结构，但是可能会出现有点第二维度很小，比如下面的例题，不需要两层for循环。 return 0;}

五、举例子

例题1、http://lx.lanqiao.cn/problem.page?gpid=T581

算法提高秘密行动

问题描述　　

小D接到一项任务，要求他爬到一座n层大厦的顶端与神秘人物会面。这座大厦有一个神奇的特点，每层的高度都不一样，同时，小D也拥有一项特殊能力，可以一次向上跳跃一层或两层，但是这项能力无法连续使用。已知向上1高度消耗的时间为1，跳跃不消耗时间。由于事态紧急，小D想知道他最少需要多少时间到达顶层。

输入格式　　

第一行包含一个整数n，代表楼的高度。　　

接下来n行每行一个整数ai，代表i层的楼层高度（ai <= 100）。

输出格式　　

输出1行，包含一个整数，表示所需的最短时间。

样例输入 5 3 5 1 8 4

样例输出 1

数据规模此处略

http://lx.lanqiao.cn/problem.page?gpid=T581

题解

#define _CRT_SECURE_NO_WARNINGS#include <cstdio>#include <iostream>#include <string>#include <cstring>#include <stack>#include <queue>#include <vector>#include <cmath>#include <algorithm>
using namespace std;const int mod = 1000000007;const int M = 123456;//const int N = 10000;const int N = 1e5 + 10;
typedef long long ll;int a[N];int dp[N][2]; //z = f[i][j] 表示到达第i层用第j种方式需要消耗的高度为z 假设一开始是在高度为0的地方，所以f[0]都是0int n;
// 按照步数来，一步（跳or爬） 两步 只有跳 的方式区分int main(){ cin >> n; //输入楼高 for (int i = 1; i <= n; i++) scanf("%d", &a[i]); //按顺序输入每一层楼
 memset(dp, 0x3f, sizeof(dp)); //初始化所有的f动态规划数组为无穷大 dp[0][1] = dp[0][0] = 0; //跳或不跳都是从高度为0开始 for (int i = 1; i <= n; i++) { //到达第i层  dp[i][0] = min(dp[i][0], dp[i - 1][0] + a[i]);//代表在上一次是爬的基础上 再爬 dp[i][0] = min(dp[i][0], dp[i - 1][1] + a[i]);//代表在上一次是跳的基础上 再爬 dp[i][1] = min(dp[i][1], dp[i - 1][0]); //代表在上一次是爬的基础上 跳（因为跳的话，上一次只能是爬） 这个机制保证了每次都是跳 爬 不会出现跳 跳的情况 //避免一直跳，如果上一次是跳的  if (i >= 2) dp[i][1] = min(dp[i][1], dp[i - 2][0]); //代表跳两个格子，在跳一次 //这个保证了每次都是先爬后跳，只不过跳的大小不同 } int res = min(dp[n][0], dp[n][1]); //在最后一次是爬和最后一次是跳里选一个最小的 printf("%d", res); return 0;}

例题2、http://lx.lanqiao.cn/problem.page?gpid=T575

算法提高和谐宿舍2

问题描述　　

墙上有n张作品。这些作品都是宽度为1，高度不定的矩形，从左到右排成一排，且底边在同一水平线上。

宿舍评比就要来了，为了及格，我们决定买不多于m块的矩形木板，把这些作品和谐掉。要求木板也从左到右排成一排，且底边与作品的底边在同一水平线上。　　

在能够把所有作品和谐掉的前提下，我们希望这些木板的面积和最小，问最小面积和。

输入格式　　

第一行两个数n和m，表示作品数和木板数；　　

第二行n个数Hi，表示从左到右第i个作品的高度。

输出格式　　

一行一个数ans，表示答案。

样例输入

5 2

4 2 3 5 4

样例输出 22

http://lx.lanqiao.cn/problem.page?gpid=T575

题解

#include <cstdio>#include <iostream>#include <string>#include <stack>#include <queue>#include <vector>#include <cmath>#include <algorithm>#define INF 0x3F3F3F3Fusing namespace std;const int mod = 1000000007;const int M = 123456;const int N = 123;
long a[N][N] = { 0 };static long long maxl = 0;
int max(int x, int y){ return (x >= y ? x : y);}int min(int x, int y){ return (x <= y ? x : y);}
int height[N] = { 0 }, maxh[N][N] = { 0 };int f[N][N] = { 0 };
int main(){ int n,m; cin >> n >> m;//n是画的数量 m是板子的数量
 for (int i = 1; i <= n; i++) { cin >> height[i]; }
 for (int i = 1; i <= n; i++) { maxh[i][i] = height[i]; for (int j = i + 1; j <= n; j++) { maxh[i][j] = max(maxh[i][j - 1], height[j]); } }

 for (int i = 1; i <= n; i++) { f[i][1] = i * maxh[1][i]; for (int j = 2; j <=m &&j<=i ; j++) { f[i][j] = INF; for (int k = 1;k<=i-j+1 ; k++) { f[i][j] = min(f[i][j], f[i - k][j - 1] + k * maxh[i - k + 1][i]); } } } cout << f[n][m]; return 0;}