• 动态规划算法

    动态规划特征

    1. 计数问题：有多少方法可以达到目标
    2. 求最大最小值问题：路径数字或代价之和，最长序列长度
    3. 求存在性：能否找到k个数综合或状态到达目标值

    思路：多阶段决策，每个阶段做出决策，全部过程为决策序列，将动态规划原问题分解成多个相互重叠的子问题，自底向上的求解最优值

    DP性质：判断是否符合动态规划的条件，满足：

    1. 最优子结构，可划分成若干子问题，原问题包含子问题的最优解
    2. 子问题重叠，对重复出现的子问题，在第一次遇到求解并保存

    解题步骤：

    1. 找出最优解性质，并刻画其结构特征，即找出状态转移方程
    2. 递归定义最大值
    3. 自底向上求出最优解
    4. 根据计算的最优质求出最优解

    一维问题子问题的划分

    二维问题的划分

    一维问题 

     例1: 有n块石头编号为0-n-1

    一只青蛙从0开始跳到n-1石头的位置，每次只能向右跳，且如果该蛙在第i块石头上，他可以跳到ai个位置，a[]中保存了每次可以跳的步数                                                                                       问：该蛙能否跳到第n-1块石头？

    算法思想：设f[j]表示能否跳到j，为布尔型

           F[j] = 1  {F[j-1]==1 && i+a[i]>=j}      //判断当前所在位置是否跳到，且是否还能跳到第j个石头、

           F[j] = 0  else

           其中i+a[i]>=j为最后一步的距离, F[j-1]为上一步的状态。

           每次设目标为j，从0开始，每次移动将当前位置加上a[i]中跳的步数，判断能否达到目标

    1. 	bool CanJump(int A[], int n){
    2. 		bool F[n];	//保存状态
    3. 		F[0] = true;
    4. 		for(int j = 1; j//确定目标	
    5. 			f[j] = false;
    6. 			for(int i = 0;i
    7. 				if(F[j-1] && i+a[i] >=j )	//能跳到目标
    8. 					F[j] = true;		    //则将当前位置置true
    9. 			}
    10. 		}
    11. 		return F[n-1];        //返回最后一块石头的状态
    12. }

    例2：求 数列中最大连续子序列之和

    状态转移方程：dp[i] = max{dp[i-1]+nums[i],dp[i-1]}；

    设当前位置为i （i>1）,且之前的序列之和dp[i-1]的数值 与 加上当前位置的数值只和大小，          选择较大的数值作为当前最大连续序列之和

    1. int maxSubArray(int nums[], int n){
    2. 	int maxsum = nums[0];
    3. 	int DP[n];
    4. 	for(int i = 0; i < n; i++){
    5. 		if(nums[i-1] > 0){
    6. 			dp[i] = nums[i] + dp[i-1];
    7. 			if(dp[i] < dp[i-1]){
    8. 				dp[i] = dp[i-1];
    9. 			}
    10. 		}
    11. 	}
    12. 	return dp[n];
    13. }

    例3. 硬币划分，有面值2，5，7元的硬币，买一本书要27，用最少的硬件组合正好付清，且不需要找零。

    算法思想：确定状态，开辟一个解空间数组保存最优值，需考虑前面的两个状态来确定当前最优解。一定有最后一枚硬币a[k],使得之前所有硬币加起来有27-a[k] 

    设金额为N，从N=27开始迭代，每次金额减去当前选择硬币面值大小，此时硬币数量+1

     所以状态转移方程：F[n] = min{F[n-a[0]]+1, F[n-a[1]]+1, F[n-a[2]]+1}

    1. int MinCoin(int N, int a[],int m){
    2. 	int dp[N];
    3. 	dp[0] = IntMax;	//设置最大值，最用找出最小解
    4.     for(int i=1; i <=N;i++){		//遍历所有金额时的硬币数量
    5. 	    for(int j = 0; j//遍历硬币
    6. 			if((dp[i-a[j]]+1 < dp[i]) && (i-a[j]>0))
    7. 				dp[i] = dp[i-a[j]]+1;
    8. 		} 
    9. 	}
    10. 	if(dp[N] == IntMax){
    11. 		return -1;
    12. 	}
    13. 	return dp[N];
    14. }

    二维问题

    例1：给定网络，从左上角(0，0)出发，只能向左或向下移动，问有多少方法能走到右下角

    算法思想：子问题设dp[i][j]为当前有多少方式走到(i,j),则对任意的位置(i，j)的状态转移方程为：

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

    可以想象如果是从两个不同的平行宇宙达到该位置，则有上面和左边两个不同的路径

    在初试位置设dp[0][0]=1，即计算左边位置已有的方法总和加上上面位置已有的方法数量总和为当前位置的总和。

    1. int Ways(int m,int n){
    2. 	int dp[m][n];
    3. 	dp[0][0] = 1;        //初始位置路线数量为1
    4. 	for(int i=1;i<=M;i++){        //对网格地图进行遍历
    5. 		for(int j = 1;j<=N;j++)
    6. 			dp[i][j] = dp[i-1][j]+dp[i][j-1];
    7. 	}
    8. 	return dp[m][n];        
    9. }

    例2：LCS最长公共子序列

    两个字符串分别是“ABCBDAB”和“BDCABC”,其中最长公共子序列长度为4，则任意两个字符串，求其中最长公共子序列长度

    算法思想：若s1[i]==s2[i],有当前相等的长度加1，即将之前的状态长度更新,则状态转移方程为：

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

    否则比较之前两个状态中较长的一个作为当前最优解

    dp[i][j] = max{dp[i-1][j],dp[i][j-1]}        s1[i]!= s2[j]

    状态转移方程： dp[i][j] = 0                                            (i=0 || j=0)

                                 dp[i][j] = dp[i-1][j-1] + 1;                   s1[i] = s2[j]

                                 dp[i][j] = max{dp[i-1][j],dp[i][j-1]}       s1[i]!= s2[j]

    且若相等则当前状态置1，否则，s1中较长状态置2，s2中较长状态置3

    从后向前递推，判断s1倒数第i个和s2倒数第j个元素向前地推，找出最长序列状态

    再通过状态数组递归求解最长公共秩序列长度

    1. const int maxsize = 10000;
    2. void LCSLength(int s1[], int s2[], int m, int n){
    3. 		int dp[maxsize][maxsize];		//最长公共子序列长度
    4. 		int b[maxsize][maxsize];		//s1,s2子序列长度比较状态
    5. 		int i,j;
    6. 		for(i = 1;i<=m; i++){
    7. 			for(j = 1;j<=n;j++){
    8. 				if(s1[i] == s2[j])
    9. 					dp[i][j] = dp[i-1][j-1]+1;	//之前公共长度+1
    10. 					b[i][j] = 1;
    11. 				else		//最长公共子序列为 s1前i-1个和s2前j-1个最长公共子序列，确定较长的状态
    12. 					if(dp[i-1][j] > dp[i][j-1])
    13. 						dp[i][j] = dp[i-1][j];
    14. 						b[i][j] = 2;
    15. 					else
    16. 						dp[i][j] = dp[i][j-1];
    17. 						b[i][j] = 3;
    18. 			}
    19. 		}
    20. }
    21. viod LCS(int i,int j){
    22. 		if(i==0 || j==0)	return;
    23. 		if(b[i][j] == 1){
    24. 			LCS(i-1,j-1);
    25. 			printf("%d",s[i]);
    26. 		}else if(b[i]lj] == 2){
    27. 			LCS(i-1,j);
    28. 		}else{
    29. 			LCS(i,j-1);
    30. 		}
    31. }

    例3：0-1背包问题

    背包问题：有M个价值各不同的珠宝，小偷偷每个珠宝的时间也各不同，要在保安发现之前赶紧把珠宝尽可能多地装进背包，同时也必须保证背包内珠宝总价值最大

    设：背包大小为M[][]，t时刻偷窃珠宝的价值为V[100],每个珠宝偷窃的时间为time[t]

    t时刻偷窃第i个珠宝，当前时间为t，则对当前珠宝进行判断，

    设上次偷窃完背包内价值加上本次这个珠宝价值v[i]为: m[i-1][ t-time[i] ]，

    如果不偷窃该珠宝，则为: m[i-1][t]

    状态转移方程：M[i] [j]= max{ v[i]+m[i-1][j-time[i] , m[i-1][t]}

    1. int TotalTime, num;    //设置总时间和珠宝数量
    2. int value[100],time[100],m[1000][1000];
    3. int main(){
    4.     printf("输入总时间和珠宝数量\n")
    5.     scanf("%d,%d",&TotalTime,&num);
    6.     printf("输入每个珠宝的时间和珠宝价值\n")
    7.     for(int i = 0; i
    8.         scanf("%d,%d",&time[i],&value[i]);
    9.         printf("\n");
    10.     }
    11.     for(int i = 0; i
    12.         for(int t=TotalTime;t>0;t--){    //剩余时间
    13.             if(time[t]//当前珠宝偷窃时间足够
    14.                 int value1 = m[i-1][t-time[t]+v[i];
    15.                 int value2 = m[i-1][t];    //如果不采集，时间不变
    16.                 m[i][t] = (value1>value2 : value1?value2);
    17.             }
    18.         }        
    19.     }
    20.     printf("偷窃总价值为：%d",m[num][TotalTime]);
    21.     return 0;
    22. }

    例4：路径之和最小

    给定三角形数字阵列，选择一条自顶向下的路径，使得沿途所有数字之和最小

    2

    3,4

    6,5,7

    4,1,8,3           其中最小路径之和为：2+3+5+1 = 11

    算法思想：自底向上计算最优解，从最下面一行元素开始，每次移动可以向上移动，也可以向左右移动，每次移动取三个状态的最小值加上当前位置元素作为当前最优解

    状态转移方程：dp[i][j] = min{dp[i-1][j] , dp[i-1][j-1] , dp[i-1][j+1]}+a[i][j];

    从最后一行往上回溯遍历，选择上一行相邻的每个数据的状态加上当前数值大小

    1. int MinDP(int a[][], int n){
    2. 	int dp[maxsize][maxsize];
    3. 		for(int i = n; i>0;i--){
    4. 			dp[n][j] = a[n][i];	
    5. 			for(int j = 0; j
    6. 				dp[i][j] = math.min(dp[i-1][j],dp[i-1][j+1],dp[i-1][j-1])+a[i][j];
    7. 			}
    8. 		}
    9. 		int result = dp[1][1];	//从最下面加到一个元素为最终结果
    10. 		return result;
    11. }

    例5：某地有未填平的海域，需要n块石头填海，每块石头消耗体力为k[i]，当前体力值为C，每块石头的体积为Vi，输入三个整数：V(需填的体积)，n(石头数)，C(体力乘积)

    第二行输入每块石头体积和消耗的体力

    若能填平输出剩余体力，否为输出“Impossible!”

    算法思想：现在所有石头体积中将最大的石头填平海面，再选出所有方案中体力消耗最小的状态作为最优解。

    状态转移方程：f[j] = max{f[j], f[j-k[i]]+v[i]}。j为当前剩余体力

    对每块石头可以选择填或不填，填入则海面剩余体积要减去石头的体积同时剩余体力值要减去当前石头消耗的体力

    1. #define MaxSize 10000;
    2. int v[MaxSize], k[MaxSize],f[MaxSize];
    3. int main(){
    4. 	int n, C ,V;
    5. 	scanf("%d,%d,%d",&n,&C,&V);
    6. 	for(int i = 1; j<=n; i++){
    7. 		scanf("%d,%d",&v[i],&k[i]);
    8. 	}
    9. 	int answer = 100000;                    //取最大值作为求最小值的初始解
    10. 	for(int i = 1; i<=n;i++){
    11. 		for(int j = C;j > 0 && j>=k[i] ;j--){	//体力从C开始，且保证石头能搬得动
    12. 			f[j] = math.max(f[j], f[j-k[i]]+v[i]);
    13. 			if(f[j] >= V){                  //当前填完的体积大于还需填平的体积
    14. 				answer = min{answer, j};	//取最小体力作为结果
    15. 			}
    16. 		}
    17. 	}
    18. 	if(answer > C)	//超过初始体力
    19. 		printf("Impossible!");
    20. 	printf("%d",c-answer);		//输出消耗体力
    21. 	return 0;
    22. }

    例6：租用游艇问题

    有N个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游任何一个位置归还游艇。游艇出租站i到j之间的租金为r(i,j)，计算从出租站1到n租船需要的最少租金。

    状态转移方程：dp[i][j] = min{dp[i][k] + dp[k+1][j] ,  dp[i][j]}

    1. #define MaxSize 10000;
    2. void dp(int n){
    3. 		int temp;
    4. 		int dp[MaxSize][MaxSize], r[MaxSize];    //dp为1-N不同出租站的租用状态，r为租金
    5. 		for(int i=1;i<=n;i++){
    6. 			for(int j=1;j<=n;j++){
    7. 				scanf("%d",&r[i][j]);        //r[1][n]=Max
    8. 				dp[i][j] = r[i][j];
    9. 			}
    10. 		}
    11. 		for(int r = 2; r<=n;r++){            //从第2个站台开始作为归还点，到最后一个进行遍历
    12. 			for(int i = 1; i < n-r+1; i++){  //从开始站台到归还点之间的站台再次租用
    13. 				int j = r+i-1;               //归还点+租用站台数量作为租用次数
    14. 				for(int k = i; k < = j; k++){
    15. 					temp = dp[i][k] + dp[k+1][j];
    16. 					if(temp < dp[i][j])
    17. 						dp[i][j] = temp;
    18. 				}
    19. 			}
    20. 		}
    21. 		return dp[1][n];
    22. }

  • 相关阅读:
    leetcode 496: 下一个更大元素 I
    关于linux多线程fork的理解和学习
    利用Redis实现向量相似度搜索：解决文本、图像和音频之间的相似度匹配问题
    uniapp和vue3+ts创建自定义下拉选择框组件
    java计算机毕业设计springboot+vue游戏道具管理系统
    git原理浅析
    复习Day03：数组part03:76 . 最小覆盖子串、438. 找到z字符串z中所有字母异位词
    练习 4 Web [MRCTF2020]Ez_bypass
    线性代数学习笔记11-1：总复习Part1（CR分解、LU分解、QR分解）
    5. 最长回文子串
  • 原文地址：https://blog.csdn.net/qq_37504771/article/details/126952481