动态规划

数据结构与算法

发布日期: 2021-12-09

文章字数: 4.5k

阅读时长: 19 分

阅读次数:

动态规划

一个规模比较大的问题分成几个规模比较小的问题，然后由小的问题推导出大的问题

动态规划可以分为如下四大类，可以依次进行学习：线性动规，区域动规，树形动规，背包动规。

一个案列引入动态规划

数字三角形–递归

题目：

在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。三角形的行数大于1小于等于100，数字为 0 - 99

题解：

虽然只是一道简单的递推题，即使用循环都能做出来，但是从零开始逐渐分析，慢慢的就能体会到动态规划的用处，也让我对动态规划的理解也更加的深入。让我们一步一步的剖析这个从无到最终演变的过程。

输入：

题解：首先用最简单的二维数组存数字三角形，用递归的方式求一下结果试一下；

#include<iostream>
#include<algorithm>
using namespace std;
//d(r,j)表示第r行第j列数字
//maxSum(r,j)表示从d (r,j)到底边的最佳路径的数字之和 

int n;//数字三角形行数 
int D[101][101];//存放数字三角形 

int maxSum(int i,int j){
	if(i == n) return D[i][j];//递归出口
	int x = maxSum(i+1,j);// d(i,j)到下面一行的最优选择 
	int y = maxSum(i+1,j+1);
	return max(x,y)+D[i][j]; 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			cin>>D[i][j];
	cout<<maxSum(1,1)<<endl;//求第1行第1列到底边的最优路径 	
	return 0;
}

数字三角形–改进

思路分析：

如果采用递规的方法，深度遍历每条路径，存在大量重复计算。则时间复杂度为 2^n ,对于 n = 100 行，肯定超时。如果每算出一个MaxSum(r,j)就保存起来，下次用到其值的时候直接取用，则可免去重复计算。那么可以用O(n^2 )时间完成计算。因为三角形的数字总数是 n(n+1)/2

改进题解：

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
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;
}

数字三角形–记忆形递推

思路：

接下来是比较容易理解，也是最容易见到的递推，但是，和一般的递推有一点点不一样的是，没必要用二维maxSum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推，那么只要一维数组maxSum[100]即可,即只要存储一行的MaxSum值就可以。

ps：因为用一维数组maxSum[100]来记忆过程中的一行的MaxSum，也就是记忆形递推吧；

题解：

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
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;
}

数字三角形–空间优化

进一步考虑，连maxSum数组都可以不要，直接用D的第n行替代maxSum即可。节省空间，时间复杂度不变

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
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;
}

由一个数字三角形的案例我们简单的了解了什么是

最长上升子序列

问题描述一个数的序列ai，当a1 < a2 < … < aS的时候，我们称这个序列是上升的。对于给定的一个序列(a1 , a2 , …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入数据

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

输出要求

最长上升子序列的长度。

输入样例

7 
1 7 3 5 9 4 8

输出样例

1、把原问题分解成子问题

求以ak（k=1, 2, 3…N）为终点的最长上升子序列的长度，只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。

2、确定状态

子问题只和一个变量– 数字的位置相关。因此序列中数的位置k 就是“状态”，而状态 k 对应的“值”，就是以ak做为 “终点”的最长上升子序列的长度。状态一共有N个。

3、找状态转移方程

maxLen (k)表示以ak做为“终点”的最长上升子序列的长度那么：初始状态：maxLen (1) = 1 maxLen (k) = max { maxLen (i)：1<=i < k 且 ai < ak且 k≠1 } + 1 若找不到这样的i,则maxLen(k) = 1

题解：

```



# 最长公共子序列

输入两行字符串，求两字符串最长公共子序列

```C++
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1010;

char size1[MAXN];
char size2[MAXN];
int maxLen[MAXN][MAXN];

int main(){
	int i,j;
	/*for(i=0;i<MAXN;++i){
		size1[i] = getchar();
		if(size1[i] == '\n') break;
	}   size1[i]='\0';//最后一个字符赋值作为为c语言判断 字符串结束的依据 
	*/
	cin>>size1;
	cin>>size2;
	int length1 = strlen(size1);
	int length2 = strlen(size2);
	for( i = 0;i <= length1; i ++ )//第1列初始化为0 
		maxLen[i][0] = 0;
	for( j = 0;j <= length2; j ++ )//第1行初始化为0 
		maxLen[0][j] = 0;
	//核心解题关键 
	for( i = 1;i <= length1;i++ ) {
		for( j = 1;j <= length2;j++ ) {
			if( size1[i-1] == size2[j-1] )
				maxLen[i][j] = maxLen[i-1][j-1] + 1;
			else
				maxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]);
		}
	}
	cout << maxLen[length1][length2];

	return 0;
}

解题思路总结：

先确定问题是否能用动态规划解决，能用动规解决的问题的特点如下：

问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。
无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。

一般情况下，问题大致了解不一定能看出是否可以用动态规划解题，解题步骤大致如下：

1、把原问题分解成子问题

子问题和原问题相同或类似，子问题的解一旦求出就会被保存，所以只会求一次

2、确定状态

3、找状态转移方程

以下为刷题：洛谷:P1216

Step1：定义数组元素的含义

定义 dp[i] [j]的含义为：当走到塔尖时路经数字最大和

Step2：找出关系数组元素间的关系式（状态转移方程）

dp[i] [j] = max(dp[i+1][j],dp[i+1][j+1]);

Step3：找出初始值

初始值dp[i]（最后一行）根据输入值变化而变化

题解代码如下：

#include<bits/stdc++.h>
using namespace std;

int dp(int m){
	vector<vector<int>> dp(m, vector<int>(m));
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j <= i; ++j) {
	    	cin>>dp[i][j];
		}
	}	

	for (int i = m-2; i >= 0; --i) {
	    for (int j = 0; j <= i; ++j) {
	        dp[i][j] += max(dp[i+1][j],dp[i+1][j+1]);
	    }
	}
	return dp[0][0];
}

int main(void){
	int r,sum;
	cin>>r;
	sum=dp(r);
	cout<<sum;
	return 0;
}

一维DP：青蛙跳台阶

问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

步骤一、定义数组元素的含义

定义 dp[i] 的含义为：跳上一个 i 级的台阶总共有 dp[i] 种跳法

步骤二、找出数组元素间的关系式

dp[n] = dp[n-1] + dp[n-2]

步骤三、找出初始条件

dp[0] = 0、dp[1] = 1、dp[2] = 2

即 n <= 2 时，dp[n] = n.

题解代码

//简单代码写出题解，当然它还可以优化；
int f( int n ){
    if(n <= 2)
    return n;
    // 先创建一个数组来保存历史数据
    int[] dp = new int[n+1];
    // 给出初始值
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    // 通过关系式来计算出 dp[n]
    for(int i = 2; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    // 把最终结果返回
    return dp[n];
}

二维数组DP：最多路径数

问题描述

一个机器人位于一个 m x n 网格的左上角

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角

问总共有多少条不同的路径？

步骤一、定义数组元素的含义

由于我们的目的是从左上角到右下角一共有多少种路径，那我们就定义 dp[i] [j]的含义为：当机器人从左上角走到(i, j) 这个位置时，一共有 dp[i] [j] 种路径。

注意，这个网格相当于一个二维数组，数组是从下标为 0 开始算起的，所以右下角的位置是 (m-1, n - 1)，所以 dp[m-1] [n-1] 就是答案。

步骤二：找出关系数组元素间的关系式

想象以下，机器人要怎么样才能到达 (i, j) 这个位置？由于机器人可以向下走或者向右走，所以有两种方式到达

一种是从 (i-1, j) 这个位置走一步到达

一种是从(i, j - 1) 这个位置走一步到达

因为是计算所有可能的步骤，所以是把所有可能走的路径都加起来，所以关系式是

dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]

步骤三、找出初始值

显然，当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的，相当于计算机图中的最上面一行和左边一列。因此初始值如下：

dp[0] [0….n-1] = 1; // 相当于最上面一行，机器人只能一直往右走

dp[0…m-1] [0] = 1; // 相当于最左面一列，机器人只能一直往下走

题解代码：

//简单代码写出题解，当然它还可以优化；
public static int uniquePaths(int m, int n) {
    if (m <= 0 || n <= 0) {
        return 0;
    }

    int[][] dp = new int[m][n];
    // 初始化
    for(int i = 0; i < m; i++){
      dp[i][0] = 1;
    }
    for(int i = 0; i < n; i++){
      dp[0][i] = 1;
    }
        // 推导出 dp[m-1][n-1]
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

C++版的，虽然语言不同，但思维差不多的

int uniquePaths(int m, int n) {
    //创建m×n的二维数组，而且可以通过v[i][j]的方式来访问元素（vector支持下标访问元素）
    //定义了一个vector容器，元素类型为vector<int>，初始化为包含m个vector<int>对象，每个对象都是一个新创立的vector<int>对象的拷贝，而这个新创立的vector<int>对象被初始化为包含n个0。
    vector<vector<int>> dp(m, vector<int>(n));
    // 初始化
    for (int i = 0; i < m; ++i) {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n; ++j) {
        dp[0][j] = 1;
    }
    // 推导出dp[m-1][n-1]
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

代码优化：

前面的基础解法中空间复杂度为O(n * m)，下面我们来讲解如何优化成 O(n)。

根据公式

dp[i][j]= dp[i-1][j] + dp[i][j-1]

，我们可以知道，当我们要计算第 i 行的值时，除了会用到第 i - 1 行外，其他第 1 至第 i-2 行的值我们都是不需要用到的，只需要用一个一维的 dp[] 来保存一行的历史记录就可以了。然后在计算机的过程中，不断着更新 dp[] 的值。

以往的二维的时候， dp[i][j] = dp[i-1] [j]+ dp[i][j-1]。现在转化成一维，不就是 dp[i] = dp[i] + dp[i-1] 吗？

即 dp[1] = dp[1] + dp[0]，而且还动态帮我们更新了 dp[1] 的值。因为刚开始 dp[i] 的保存第一行的值的，现在更新为保存第二行的值。

dp[i] = dp[i-1] + dp[i]

dp[i-1] 相当于之前的 dp[i-1][j]，dp[i] 相当于之前的 dp[i][j-1]。

//优化代码如下，时间复杂度O（m*n），空间复杂度O（n）
public static int uniquePaths(int m, int n) {
    if (m <= 0 || n <= 0) {
        return 0;
    }

    int[] dp = new int[n]; 
    // 初始化
    for(int i = 0; i < n; i++){
      dp[i] = 1;
    }

        // 公式：dp[i] = dp[i-1] + dp[i]
    for (int i = 1; i < m; i++) {
        // 第 i 行第 0 列的初始值
        dp[0] = 1;
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j-1] + dp[j];
        }
    }
    return dp[n-1];
}

最后要求的答案就是：dp[n-1]

二维数组DP：最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

步骤一、定义数组元素的含义

由于我们的目的是从左上角到右下角，最小路径和是多少，那我们就定义 dp[i] [j]的含义为：**当机器人从左上角走到(i, j) 这个位置时，最下的路径和是 dp[i] [j]**。那么，dp[m-1] [n-1] 就是我们要的答案了。

不过这次不是计算所有可能路径，而是计算哪一个路径和是最小的，那么我们要从这两种方式中，选择一种，使得dp[i] [j] 的值是最小的，显然有

dp[i] [j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j];// arr[i][j] 表示网格总的值

步骤三、找出初始值

dp[0] [j] = arr[0] [j] + dp[0] [j-1]; // 相当于最上面一行，机器人只能一直往左走

dp[i] [0] = arr[i] [0] + dp[i] [0]; // 相当于最左面一列，机器人只能一直往下走

题解代码：

public static int uniquePaths(int[][] arr) {
    int m = arr.length;
    int n = arr[0].length;
    if (m <= 0 || n <= 0) {
        return 0;
    }

    int[][] dp = new int[m][n];
    // 初始化
    dp[0][0] = arr[0][0];
    // 初始化最左边的列
    for(int i = 1; i < m; i++){
      dp[i][0] = dp[i-1][0] + arr[i][0];
    }
    // 初始化最上边的行
    for(int i = 1; i < n; i++){
      dp[0][i] = dp[0][i-1] + arr[0][i];
    }
     // 推导出 dp[m-1][n-1]
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
        }
    }
    return dp[m-1][n-1];
}

O(n*m) 的空间复杂度可以优化成 O(min(n, m)) 的空间复杂度的，不过这里先不讲

hard 题目

问题描述：

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符删除一个字符替换一个字符

示例：
输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

本文参考来源：

冰冰的小屋

https://binbincome.github.io/2021/12/09/shu-ju-jie-gou-yu-suan-fa/dong-tai-gui-hua/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源冰冰的小屋 !

动态规划

操作系统01

2021-12-09 计算机基础

操作系统

如何求解金矿问题

2021-12-08 数据结构与算法

数据结构算法题