DP总结

2021年09月15日 阅读数:1
这篇文章主要向大家介绍DP总结,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

最近也写了一些dp,感受对于状态的转移有了点小小的体会ios

像以前写的都是一些经典的dp背包啊,LIS之类的,最近写了一些感受更在于寻找状态的dp,固然也不是很难,太难的我也不会。算法

目标答案必定是由前一个状态来表示从而地推,dp的难处就在于如何用简单的数组来表示复杂的状态转移的过程,这也是咱们要作和练习的事情。数组

因为一些复杂状态的题目(状态压缩之类的),有时候咱们不得不对数组多开一维(或者是利用二进制位运算)来实现这个状态,把这个复杂的状态markdown

表示出来,利用状态转移方程地推下去便可。数据结构

 

谈谈我学的dp,主要都是线性dp,难点的我也没学过ide

一类就是一维数组便可实现的线性dp,通常相对简单点,由于状态容易表示出来,通常是对于一串数字进行的操做,也不乏抽象为别的东西。函数

一类是区间dp,为了求得一个大区间的最优解咱们一般要知道全部小区间的最优解才能进行下去,通常用二维数组dp[i][j]表示区间【i,j】的最优解,优化

对于此类dp有平行不等式的优化操做我暂时不会,经典问题有合并石子,最大累乘等。spa

一类是状态压缩dp,真正的装压dp目前还未掌握(往后学会在更),先是针对于一些简单的01状态而言,通常能够用dp[n][0]-dp[n][1]来简单的表示这两种状态对应的最优解,3d

经典问题有开关灯等

 

 

在看别人博客时看到了"我为人人"和"人人为我"的两种dp递推形式,
dp[i]+=dp[i-1]+dp[i-1]/dp[i+x]+=dp[i];

意思就是一种方程是当前的状态是由前面所计算出的状态决定的,一种是由当前的状态直接推出后面的某些状态。

例如斐波那契数 dp[i]=dp[i-1]+dp[i-2]  显然他是一我的人为我,用我为人人得话显然不是正确选择。

例:数字三角形(POJ 1163)
Language:Default
The Triangle
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 45053   Accepted: 27208

Description

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

(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

Input

Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

Output

Your program is to write to standard output. The highest sum is written as an integer.

Sample Input

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

Sample Output

30

Source

基本思路

用二维数组存放数字三角形。

D( r, j) : 第r行第 j 个数字(r,j从1开始算)
MaxSum(r, j) : 从D(r,j)到底边的各条路径中,
最佳路径的数字之和。
问题:求 MaxSum(1,1)

典型的递归问题。
D(r, j)出发,下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形:

if ( r == N)
    MaxSum(r,j) = D(r,j) else MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j)
 

而后你会发现:
DP总结_递归

为何超时

重复计算

若是采用递规的方法,深度遍历每条路径,存在大量重复计算。则时间复杂度为 2n,对于 n = 100 行,确定超时。

改进

若是每算出一个MaxSum(r,j)就保存起来,下次用到其值的时候直接取用,则可免去重复计算。那么能够用O(n2)时间完成计算。由于三角形的数字总数是 n(n+1)/2

改进代码

#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std; int D[MAX][MAX]; int n; int maxSum[MAX][MAX]; int MaxSum(int i, int j) { if (maxSum[i][j] != -1) return maxSum[i][j]; if (i == n) maxSum[i][j] = D[i][j]; else { int x = MaxSum(i + 1, j); int y = MaxSum(i + 1, j + 1); maxSum[i][j] = max(x, y) + D[i][j]; } return maxSum[i][j]; } int main() { int i, j; cin >> n; for (i = 1; i <= n; i++) for (j = 1; j <= i; j++) { cin >> D[i][j]; maxSum[i][j] = -1; } cout << MaxSum(1, 1) << endl; }

 

 

转化为递推

“人人为我”型递推

#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;

int D[MAX][MAX]; int n; int maxSum[MAX][MAX]; int main() {  int i, j;  cin >> n;  for (i = 1; i <= n; i++)  for (j = 1; j <= i; j++)  cin >> D[i][j];  for (int i = 1; i <= n; ++i)  maxSum[n][i] = D[n][i];  for (int i = n - 1; i >= 1; --i)  for (int j = 1; j <= i; ++j)  maxSum[i][j] = max(maxSum[i + 1][j], maxSum[i + 1][j + 1]) + D[i][j];  cout << maxSum[1][1] << endl; }

 

这里说的人人为我型递归就是在求DP[i][j]的过程当中, 使用DP[i-1][1]→DP[i - 1][i - 1]来推到出DP[i][j];

“我为人人”型递归

#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;

int D[MAX][MAX]; int n; int maxSum[MAX][MAX]; int main() {  int i, j;  cin >> n;  for (i = 1; i <= n; i++)  for (j = 1; j <= i; j++)  cin >> maxSum[i][j];  for (int i = 1; i < n; i++)  {  for (int j = 1; j <= i; j++)  {  maxSum[i + 1][j] = max(maxSum[i + 1][j], maxSum[i + 1][j] + maxSum[i][j]);  maxSum[i + 1][j + 1] = max(maxSum[i + 1][j + 1], maxSum[i + 1][j + 1] + maxSum[i][j]);  }  }  int maxx = -9999999999;  for (int i = 1; i <= n; i++)  maxx = max(maxx, maxSum[n][i]);  cout << maxx << endl; }

 

这里说的人人为我型递归就是在求DP[i][j]的过程当中, 求出DP[i + 1][j]和DP[i + 1][j +1]的其中一个解。

空间优化

不必用二维maxSum数组存储每个MaxSum(r,j),只要从底层一行行向上递推,那么只要一维数组maxSum[100]便可,即只要存储一行的MaxSum值就能够。

进一步考虑,连maxSum数组均可以不要,直接用D的第n行替代maxSum便可。

节省空间,时间复杂度不变
#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std; int D[MAX][MAX]; int n; int * maxSum; int main() { int i, j; cin >> n; for (i = 1; i <= n; i++) for (j = 1; j <= i; j++) cin >> D[i][j]; maxSum = D[n]; //maxSum指向第n行 for (int i = n - 1; i >= 1; --i) for (int j = 1; j <= i; ++j) maxSum[j] = max(maxSum[j], maxSum[j + 1]) + D[i][j]; cout << maxSum[1] << endl; }

 

总结三种动态规划的形式

人人为我

DP总结_最优解_02

状态i的值Fi由若干个值已知的状态值Fk,Fm,..Fy推出,如求和,取最大值

我为人人

DP总结_#include_03

状态i的值Fi在被更新(不必定是最终求出)的时候,依据Fi去更新(不必定是最终求出)和状态i相关的其余一些状态的值Fk,Fm,..Fy

注意:在选取最优备选状态的值Fm,Fn,…Fy时,有可能有好的算法数据结构能够用来显著下降时间复杂度

记忆型递归

优势:只通过有用的状态,没有浪费。递推型会查看一些没用的状态,有浪费

缺点:可能会因递归层数太深致使爆栈,函数调用带来额外时间开销。没法使用滚动数组节省空间。整体来讲,比递推型慢。

 

关于人人为我和我为人人合适的使用,

当推导当前状态时,是由前面几个固定数量的状态推导而来的,通常使用人人为我,由于这我的好找。

而当推导这个状态时,决定这个状态的状态个数可能没法肯定,须要根据具体状况挨个枚举,这样若是非要写成人人为个人话不只代码丑效率也低,

这时考虑我为人人,若是根据这个状态能推导出全部的由他引伸出的状态,显然咱们应该采用我为人人的方法。