[dp] 动态规划学习路线与笔记 | 动态规划习题集

一时失言乱红尘 2023-06-13 11:22 33阅读 0赞

> 本文记录博主dp的系统学习路线与笔记，但博主之前有接触过DP，只是未真正的系统学习过，有一丢丢的基础
> 
> 1.  有很多事前人已经做了，就不必重复做了
> 2.  有很多坑我已经踩过了，你就尽量不要踩了

> 【学习路线】如果不想看博主的笔记，可以直接按照这个顺序学习
> 
> 1.  对动态规划有一个初步的了解，只看问题引入的部分：[什么是动态规划？动态规划的意义是什么？][Link 1]
> 2.  B站的UP主动态规划入门课，通俗易懂：[动态规划第一讲][Link 2]
> 3.  [动态规划第二讲][Link 3]的第一题
> 4.  一位博主，总结的很不错：[告别动态规划，DP连刷 40 道题，我总结出了这些套路！这应该是把动态规划讲的最后的文章了][DP_ 40]
> 5.  [动态规划第二讲][Link 3]第二题
> 6.  二维dp问题：[01背包问题][01]

### 文章目录 ###

*  dp引入：换钱（一维dp）
 *  外卖小哥在一段时间内赚最多的钱（一维dp）
 *  选出一组不相邻的数字且和最大（一维dp）
 *  \[总结\] DP的解题经验
 *  能不能凑出正整数s（二维dp）
 *  01背包问题（二维dp）
 *  dp有哪些类型

# dp引入：换钱（一维dp） #

> 原文链接：[什么是动态规划？动态规划的意义是什么？][Link 1])

【问题】你想把某宝里的**666块**换成现金，而且想换来的钱的**总数最少**，因为你的钱包快装不下了

【生活中的做法】从最大的面额开始换，以此可以获得数量最少的钞票，共10张。这种思想叫贪心，每经过一次，它会尽量让数值变得更小

666 = 6 ∗ 100 + 1 ∗ 50 + 1 ∗ 10 + 1 ∗ 5 + 1 ∗ 1 666=6\*100+1\*50+1\*10+1\*5+1\*1 666=6∗100\+1∗50\+1∗10\+1∗5\+1∗1

【贪心的方法是对的吗？】如果钱的面额够科学，贪心就是对的。但是遇到这种情况：一个国家的钞票面额只有1、5、11。那我们这次用贪心来换15块

1.   15 = 1 ∗ 11 + 4 ∗ 1 15=1\*11+4\*1 15=1∗11\+4∗1，用贪心换得5张钞票
2.   15 = 3 ∗ 5 15=3\*5 15=3∗5，但最少的情况是这个，换得3张钞票

【贪心错在哪里？】鼠目寸光，只考虑了眼前的情况

【解决方案】我们用f(n)表示`换n块所需的最小钞票的数量`，那我们就有以下的情况

1.   f ( 1 ) = 1 f(1)=1 f(1)=1：换1块钱，就只要一张1块
2.   f ( 4 ) = 4 f(4)=4 f(4)=4：换4块钱，要4张1块
3.   f ( 5 ) = 1 f(5)=1 f(5)=1：换5块钱，就只要1张5块
4.   f ( 10 ) = 2 f(10)=2 f(10)=2：换10块钱，要2张5块
5.   f ( 11 ) = 1 f(11)=1 f(11)=1：换11块钱，就只需要1张11块

理解的话，我们来换一下15块

1.   c o s t ( 15 ) = f ( 11 ) + f ( 4 ) = 1 + 4 = 5 cost(15)=f(11)+f(4)=1+4=5 cost(15)=f(11)\+f(4)=1\+4=5：这种策略要5张
2.   c o s t ( 15 ) = f ( 5 ) + f ( 10 ) = f ( 5 ) + f ( 5 ) + f ( 5 ) = 3 cost(15)=f(5)+f(10)=f(5)+f(5)+f(5)=3 cost(15)=f(5)\+f(10)=f(5)\+f(5)\+f(5)=3：这种策略要3张
3.   c o s t ( 15 ) = f ( 1 ) + f ( 14 ) = 1 + 4 = 5 cost(15)=f(1)+f(14)=1+4=5 cost(15)=f(1)\+f(14)=1\+4=5：这种策略只要5张

那我们要的就是3个中最小的情况，于是有公式：

`f(n)=min{ f(n-1), f(n-5), f(n-11) } +1`

有了这个公式怎么暴力求解呢？

int f_0(int n) {  //用递归暴力求解
    	int mincost = 65535;
    	if (n==0) return 0;
    	if (n>=1) mincost = min(mincost, f_0(n-1)+1);
    	if (n>=5) mincost = min(mincost, f_0(n-5)+1);
    	if (n>=11) mincost = min(mincost, f_0(n-11)+1);
    
    	printf("f[n]=%d\n", n, mincost);
    	return mincost;
    }

此过程会生成一个递归树，由于最小面额为1，所以树的高度为n，则把树当成满二叉树来算结点总数 2 n − 1 2^n-1 2n−1，故此方法的时间复杂度为 O ( 2 n ) O(2^n) O(2n)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]

改良1：用数组保存之前的计算结果，避免重复计算，复杂度O(n)。这就是dp，暂时可以把dp理解成用数组记录历史记录的递归或递推

int min(int a, int b) { 
        return a>b?b:a;
    }
    int f_1(int n) {  
        int i, mincost, f[105];
        f[0]=0;
        for (i=1; i<=n; ++i) {  //递推的方式：从下往上算
            mincost = 65535;
            if (i>=1) mincost = min(mincost, f[i-1]+1);
            if (i>=5) mincost = min(mincost, f[i-5]+1);
            if (i>=11) mincost = min(mincost, f[i-11]+1);
            f[i]=mincost;
        }
        return f[n];
    }
    
    
    f[105]={ 0};		 //把每次计算的值保存下来
    int f_2(int n) {  //递归的方式：从上往下找需要算的内容
    	int mincost = 65535;
    
    	if (n==0) return 0;
    
    	if (n>=1) mincost = min(mincost, f[n-1]==0 ? f_2(n-1)+1: f[n-1]+1 );
        									//看f[n-1]之前有没有算过（有个装逼名字叫：记忆化搜索）
    	if (n>=5) mincost = min(mincost, f[n-5]==0 ? f_2(n-5)+1: f[n-5]+1 );
    	if (n>=11) mincost = min(mincost, f[n-11]==0 ? f_2(n-11)+1: f[n-11]+1 );
    	
    	f[n]=mincost;
    	printf("f[%d]=%d\n", n, f[n]); //看到底计算了谁
    	return mincost;
    }

> 对比：暴力<动态规划<贪心（从效率和使用条件的角度）
> 
> 1.  【贪心】上面所提，贪心的问题在于鼠目寸光，但只要面额设置的足够科学，贪心是对的。这可以说明，使用贪心的条件是很**苛刻严格**的，要经过**严格的数学证明**，才能够确定**根据局部最优所得的结果**对不对。
> 2.  【贪心vs动态规划】但对于动态规划。它在哪种面额下都是可以的，这可以说明，动态规划(dp)的条件相比于贪心是**更不苛刻**的，正是因为贪心更严格，所以**贪心的效率更高**
> 3.  【动态规划vs暴力】从上面可以看到，动态规划**没有重复计算**、也**减去了没有必要的计算内容**。减去不必要的计算任务，我们叫剪枝。也就是说动态规划**自带剪枝**，这是动态规划优于暴力的地方。

看到这里，相信你对DP有初步的了解。如果对自己没有信心，不要立刻看DP的严格定义。继续看一些例子，加深对它的感性认识。直到你对它有所感悟的时候，而且感悟到达极点的时候，再去看别人的总结，会恍然大悟，瞬间打通所有。

# 外卖小哥在一段时间内赚最多的钱（一维dp） #

> 链接：[动态规划 (第1讲)][_1]

题目：外卖小哥想在11个小时内赚最多的钱

1.  横条前的数字：第i个外卖单子，一共有8个单子
2.  横条的长度：做该单需要花费的时间段
3.  横条上的红色数字：完成该单的报酬  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 1]

【思路】选与不选  
【抽象问题】OPT\[i\]：完成前i项单子，赚的最多的钱

1.  OPT\[1\]：完成前1项单子，最多能赚5块（完成第一单）
2.  OPT\[2\]：完成前2项单子，最多能赚5块（只做第一单）
3.  OPT\[3\]：完成前3项单子，最多能赚8快（只做第三单）
4.  OPT\[4\]：完成前4项单子，最多能赚8块（只做第三单）
5.  OPT\[8\]：怎么算？

【OPT\[8\]】完成前8项单子赚的最多的钱，那就有两种可能：对于第8项单子，我是做，还是不做

1.  做第8个单子：然后8-11的时间段就不能做别的了，所以只能做8之前的单子，这里记做pre\[8\]
2.  不做第8个单子：那就是OPT\[7\]

然后在两种情况下找到最大值，即是OPT\[8\]，于是有以下公式：  
![在这里插入图片描述][20191117102131901.png]

【pre\[\]】pre数组怎么求呢？根据每个单子的结束时间来确定

【最终答案】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 2]

# 选出一组不相邻的数字且和最大（一维dp） #

> 链接：[动态规划第二讲][Link 3]第一题

题目：在一个数组arr中，找出一组不相邻的数字，使得最后的和最大  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 3]

#include<stdio.h>
    int max(int a, int b) { 
        return a>b?a:b;
    }
    
    int dp_1(int arr[], int n) {  //非递归
    	int opt[105];
    	int i;
    	//初态
    	opt[0]=arr[0];
    	opt[1]=max(arr[0], arr[1]);
    	//通式（选、不选中的最大值）：opt[i] = max{ opt[i-1], arr[i]+opt[i-2] }
    	for (i=2; i<n; ++i) { 
    		opt[i] = max( opt[i-1], arr[i]+opt[i-2] );
    
    		printf("opt[%d]=%d\n", i, opt[i]);
    	}
    
    	return opt[n-1];
    }
    
    int opt[105] = { 0}; //保存记录
    int dp_2(int arr[], int n) {  //递归
    	int i=n-1; //arr从0开始存储
    
    	if (opt[i]!=0) return opt[i]; //计算过了
    
    	if (i==0) { 
    		opt[i]=arr[0];
    		return opt[i];
    	} else if (i==1) { 
    		opt[i]=max(arr[0], arr[1]);
    		return opt[i];
    	} else { 
    		if (opt[i-1]==0) opt[i-1] = dp_2(arr, n-1);
    		if (opt[i-2]==0) opt[i-2] = dp_2(arr, n-2);
    
    		opt[i] = max( opt[i-1], arr[i]+opt[i-2] );
    		printf("opt[%d]=%d\n", i, opt[i]);
    		return opt[i];
    	}
    }
    
    int main() { 
    	int arr[105] = { 1, 2, 4, 1, 7, 8, 3};
    	printf("%d", dp_2(arr, 7) ); //前7个数字
    	return 0;
    }

# \[总结\] DP的解题经验 #

> 原文链接：[告别动态规划，DP连刷 40 道题，我总结出了这些套路！这应该是把动态规划讲的最后的文章了][DP_ 40]

【步骤一】确定数组

1.  梳理问题的条件
2.  确定数组维度：一般影响因子有几个，数组就有几个维度
3.  准确定义数组的含义

【步骤二】找出数组元素之间的关系

1.  从末态找
2.  分析问题的过程

【步骤三】找出初始值，即出口（从初态找）

*  找初始值容易出错，有时候容易找的不完整，所以不能仅局限于在数组元素中下标>=0的程度，要多考虑几位

【注意】

1.  下标问题：下标一般存1-n，0可以作为边界检查、也不容易搞乱

# 能不能凑出正整数s（二维dp） #

> 链接：[动态规划第二讲][Link 3]第二题

【题目】给定一个正整数s, 判断一个数组arr中，是否有一组数字加起来等于s  
![在这里插入图片描述][20191119112748138.png]

【第一步】确定数组

1.  确定问题：①选数字；②数字和等于S；③问题：能不能选出这么一组数字
2.  数组维数：影响因子是①数字之和、②单个数字 --> 二维dp
3.  定义数组含义（即问题）：`Subset[k][s]：从前k个元素中选一组数字，它们的和是s，subset[k][s]等于1表示能选出来`

【第二步】确定元素间的关系  
从后往前，当前数字是选还是不选，只要其中一个能凑出，就返回true  
![在这里插入图片描述][20191119112920665.png]  
【第三步】找初始值，也就是出口

1.  s==0：空集就好了，这时候返回true
2.  k==0：只有0可以选了，如果这时候第0个数值刚好是s，则返回true，否则返回false

【代码】

#include<stdio.h>
    #include<string.h>
    
    // 从arr[]中的前k个元素中，选择一组元素，它们的和刚好等于s，则返回1
    int dp[105][105]; //数组
    int dp_rec(int arr[], int k, int s) {  //递归
    	int val1, val2;
    	
    	if (dp[k][s]!=-1) return dp[k][s]; //有历史记录，直接返回
    
    	// 递归出口
    	if (s==0) 
    		dp[k][s]=0;
    	else if (k==0) 
    		dp[k][s] = arr[0]==s;
    
    	// 通式
    	else if (arr[k]>s) //选了第k个就超出了s，那不选
    		dp[k][s] = dp_rec(arr, k-1, s);	
    	else { 
    		val1 = dp_rec(arr, k-1, s); //不选
    		val2 = dp_rec(arr, k-1, s-arr[k]); //选第k个
    		dp[k][s] =  val1 || val2;
    	}
    	
    	printf("dp[%d][%d]=%d\n", k, s, dp[k][s]);
    	return dp[k][s];
    }
    
    int main() { 
    	int i,j;
    	// 测试
    	int n=6;
    	int s=9;
    	int arr[6] = { 3, 34, 4, 12, 5, 2}; //0到n-1
    
    	memset(dp, -1, sizeof(dp));
    	printf("\n可以凑到吗？ %d\n", dp_rec(arr, n-1, s) );
    
    	for (i=0; i<n; i++) { 
    		for (j=0; j<n; j++)
    			printf("%d\t", dp[i][j]);
    		printf("\n");
    	}
    	return 0;
    }

# 01背包问题（二维dp） #

> 视频链接：[01背包问题][01]  
> 链接：[01背包在线计算器][01 1]

【题目】有n个物品及它们的重量和价格，问小偷的背包只能装下20kg，怎么装偷的最多？  
![在这里插入图片描述][20191119110642953.png]  
【步骤1】确定数组

1.  确定问题：①选物品；②物品的总重量≤W；③问题：求物品的总价值最大
2.  数组维数：影响因子是①物品的总重量、②单个物品的重量 --> 二维dp
3.  定义数组含义（即问题）：`B[k][w]：在前k个商品中选取一组商品，重量≤w，物品总价值最大为B[k][w]`

【步骤2】找出数组元素的关系  
![在这里插入图片描述][20191119110158222.png]

【步骤3】找初始值

B[0][0]->B[0][w]（第一行）都为0：没有物品时，最大价值为0
    B[0][0]->B[k][0]（第一列）都为0：有物品，没有包来装，最大价值也是0

B(k,w)数组的值：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 4]  
【代码】

#define N 5 //5个商品
    #define W 20 //背包重量
    int B[N+1][W] = { 0};
    int w[N+1] = { 0, 2,3,4,5,9}; //从1-N开始记录
    int v[N+1] = { 0, 3,4,5,8,10}; //从1-N开始记录
    void Knapsack(int B[N+1][], int w[], int v[]) { 
    	int i,j;
    	int val1, val2;
    	// 初始值（其实不用赋予初始值，B[][]数组定义时初始值即为0）
    	for (j=0; j<=W; ++j) B[0][j]=0; //第一行
    	for (i=0; i<=N; ++i) B[i][0]=0; //第一列
    	// 递推
    	for (i=1; i<=N; ++i) {  //考虑前k个物品
    		for (j=1; j<=W; ++j) {  //背包的重量
    			if ( w[i] > j ) {  //第i件物品太重，背包已经装不下了
    				B[i][j] = B[i-1][j]; //不考虑第i件
    			} else { 
    				val1 = B[i-1][j];    //不选第i件
    				val2 = B[i-1][j-w[i]]+v[i]; //选第i件
    				B[i][j] = val1>val2 ? val1 : val2;
    			}
    		}
    	}
    }

# dp有哪些类型 #

[dp有哪些种类][dp]

[Link 1]: https://mp.weixin.qq.com/s/HQ5ph4oX7-5DjQaBrEm2Ag
[Link 2]: https://www.bilibili.com/video/av16544031?share_medium=android&share_source=qq&bbid=XX56C4F57E4A0221C6A8CBF7CA8C84F94D785&ts=1573956460093
[Link 3]: https://www.bilibili.com/video/av18512769/?spm_id_from=333.788.videocard.0
[DP_ 40]: https://blog.csdn.net/m0_37907797/article/details/102995091
[01]: https://www.bilibili.com/video/av36136952?share_medium=android&share_source=qq&bbid=XX56C4F57E4A0221C6A8CBF7CA8C84F94D785&ts=1574035856255
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191117092133117.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[_1]: http://www.bilibili.com/video/av16544031?share_medium=android&share_source=qq&bbid=XX56C4F57E4A0221C6A8CBF7CA8C84F94D785&ts=1573956460093
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191117100659727.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[20191117102131901.png]: https://img-blog.csdnimg.cn/20191117102131901.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191117102240962.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191117131812821.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[20191119112748138.png]: https://img-blog.csdnimg.cn/20191119112748138.png
[20191119112920665.png]: https://img-blog.csdnimg.cn/20191119112920665.png
[01 1]: https://misakasister.github.io/Online_0-1_Knapsack/index.html
[20191119110642953.png]: https://img-blog.csdnimg.cn/20191119110642953.png
[20191119110158222.png]: https://img-blog.csdnimg.cn/20191119110158222.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191119110600519.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[dp]: https://www.cnblogs.com/Renyi-Fan/p/9285495.html