devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法——动态规划（新）

作者：小丑西瓜9 | 2024-02-24 23:36:10

赞

踩

算法——动态规划（新）

什么是动态规划？

动态规划算法的基本思想-求解步骤-基本要素和一些经典的动态规划问题【干货】-CSDN博客

矩阵动态规划/单表动态规划

一、三步问题

面试题 08.01. 三步问题 - 力扣（LeetCode）

思路

我们要知道，走楼梯，前三个阶梯步数已经知道，那我们若是想走到第四楼，还需要一个个推吗？

走到4层，我们有三种方法

1.从一楼出发，这样只需要走3层即可。

2.从二楼出发，这样只需要走2层即可。

3.从三楼出发，这样只需要走1层即可。

所以在此问题中，我们要找到到达n个阶梯时，离n个阶梯最近的n-1，n-2，n-3的阶梯的最短路径。并且以此来递推出走到第n个阶梯的最短距离。

代码

  1.  int waysToStep(int n) {
  2.         const int MOD=1e9+7;
  3.         if(n==1||n==2) return n;
  4.         if(n==3) return 4;
  5.         vector<int> dp(n+1);
  6.         dp[1]=1,dp[2]=2,dp[3]=4;
  7.         for(int i=4;i<=n;i++)
  8.         {
  9.             dp[i]=((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;
  10.         }
  11.         return dp[n];
  12.     }

二、使用最小花费爬楼梯

LCR 088. 使用最小花费爬楼梯 - 力扣（LeetCode）

思路

这也是个动态规划的题目，从底层楼梯爬到最上层，那我们建立表呢？

——设一个dp表，dp[i]表示到第i层需要花费的最少的钱。

由于付一次钱，就可以爬一层或者两层楼梯，所以我们需要比较的是到第i-1层和到第i-2层最小的值————min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]) 因此这就是我们的状态转移方程。

状态转移方程就是要把握到达每一步的值从哪里来？——然后比较出最小的那一步的值，依次类推，最后得出到达第i层最小的值。

代码

  1. int minCostClimbingStairs(vector<int>& cost) {
  2.         int len=cost.size();
  3.         vector<int> dp(len+1);
  4.         if(len==1) return cost[0];
  5.         if(len==2) return min(cost[0],cost[1]);//返回两个中的最小值
  6.         dp[0]=0,dp[1]=0;
  7.         for(int i=2;i<=len;i++)
  8.         {
  9.             dp[i]=min(cost[i-1]+dp[i-1],dp[i-2]+cost[i-2]);
  10.         }
  11.         return dp[cost.size()];
  12.     }

三、解码方法

91. 解码方法 - 力扣（LeetCode）

思路

这里我们知道判断就只有两个，一个是单个数字，一个是两个数字，所以我们也可以按照动态规划的方式，由第n-1个和第n-2个推出第n个的值。

代码

  1. int numDecodings(string s) {
  2.         int n=s.size();
  3.         vector<int> dp(n+1);
  4.         dp[0]=1;
  5.         for(int i=1;i<=n;i++)
  6.         {
  7.             if(s[i-1]!='0') dp[i]+=dp[i-1];//单个字母不为0，那么就往上加,一个字母就往前加一个
  8.             if(i>1&&s[i-2]!='0'&&(s[i-2]-'0')*10+(s[i-1]-'0')<=26) dp[i]+=dp[i-2];//两个字母就加前两个的
  9.         }
  10.         return dp[n];
  11.     }

四、不同路径

LCR 098. 不同路径 - 力扣（LeetCode）

思路

首先，我们知道，只能向右或者向下行走，那么我们可以通过动态规划得出转移方程

dp[i][j]=dp[i][j-1]+dp[i-1][j],其中dp表代表的是到达i处的路径数。

初始化呢？——第一行和第一列都只有1，然后通过状态转移方程即可得出最后一个位置的值，也就是打到终点的路径数。

代码

  1. int uniquePaths(int m, int n) {
  2. 	vector<vector<int>> dp(m, vector<int>(n));
  3.     if(m==1&&n==1)
  4.         return 1;
  5. 	for (int i = 1; i < n; i++)
  6. 	{
  7. 		dp[0][i] = 1;
  8. 	}
  9. 	for (int i = 1; i < m; i++)
  10. 	{
  11. 		dp[i][0] = 1;
  12. 	}
  13. 	for (int i = 1; i < m; i++)
  14. 		for (int j = 1; j < n; j++)
  15. 			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  16. 	return dp[m - 1][n - 1];
  17. }

五、不同路径II

63. 不同路径 II - 力扣（LeetCode）

思路

思路和不同路径的思路一样，只不过需要判断障碍物的位置，若是有障碍物，那么就直接将障碍物所在的dp表的值定为0，表明到此位置的路径数为0，无法到达。

代码

  1.  int numDecodings(string s) {
  2.         int n=s.size();
  3.         vector<int> dp(n+1);
  4.         dp[0]=1;
  5.         for(int i=1;i<=n;i++)
  6.         {
  7.             if(s[i-1]!='0') dp[i]+=dp[i-1];//单个字母不为0，那么就往上加,一个字母就往前加一个
  8.             if(i>1&&s[i-2]!='0'&&(s[i-2]-'0')*10+(s[i-1]-'0')<=26) dp[i]+=dp[i-2];//两个字母就加前两个的
  9.         }
  10.         return dp[n];
  11.     }

六、珠宝的最高价值

LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

思路

类比于不同路径的求法，还是通过动态规划，分清楚每个位置的最高价值从哪里来，列出状态转移方程即可。

代码

  1.  int jewelleryValue(vector<vector<int>>& grid) {
  2.         int m=grid.size(),n=grid[0].size();
  3.         vector<vector<int>> dp(m+1,vector<int>(n+1));
  4.         for(int i=1;i<=m;i++)
  5.             for(int j=1;j<=n;j++)
  6.                 dp[i][j]=grid[i-1][j-1]+max(dp[i-1][j],dp[i][j-1]);
  7.         return dp[m][n];
  8.     }

七、下降路径的最小和

931. 下降路径最小和 - 力扣（LeetCode）

思路

此处的方法同上几道题的想法，只不过在边界的时候需要进行判断若是在边界，则是另一种的判断方法，不是边界则就按照正常的方法去记录

代码

  1. int minFallingPathSum(vector<vector<int>>& matrix) {
  2.         int m=matrix.size(),n=matrix[0].size();
  3.         vector<vector<int>> dp(m,vector<int>(n));
  4.         for(int i=0;i<n;i++)
  5.         {
  6.             dp[0][i]=matrix[0][i];//初始化
  7.         }
  8.         for(int i=1;i<m;i++)
  9.         {
  10.             for(int j=0;j<n;j++)
  11.             {
  12.                 int min=dp[i-1][j];//假定最小的就是正对的上一个数字
  13.                 if(j-1>=0&&dp[i-1][j-1]<min)
  14.                 {
  15.                     min=dp[i-1][j-1];
  16.                 }
  17.                 if(j+1<n&&dp[i-1][j+1]<min)
  18.                 {
  19.                     min=dp[i-1][j+1];
  20.                 }
  21.                 dp[i][j]=matrix[i][j]+min;
  22.             }
  23.         }
  24.         int Min=dp[m-1][0];
  25.         for(int i=1;i<n;i++)
  26.         {
  27.             Min=min(Min,dp[m-1][i]);
  28.         }
  29.         return Min;
  30.     }

八、最小路径和

LCR 099. 最小路径和 - 力扣（LeetCode）

思路

此处同上，仅需要先判断出边界的大小，然后依次取最小的即可。

代码

  1. int minPathSum(vector<vector<int>>& grid) {
  2.         int m=grid.size(),n=grid[0].size();
  3.         vector<vector<int>> dp(m,vector<int>(n));
  4.         dp[0][0]=grid[0][0];
  5.         for(int i=1;i<n;i++)//初始化第一行
  6.         {
  7.             dp[0][i]=dp[0][i-1]+grid[0][i];
  8.         }
  9.         for(int i=1;i<m;i++)//初始化第一列
  10.         {
  11.             dp[i][0]=grid[i][0]+dp[i-1][0];
  12.         }
  13.         for(int i=1;i<m;i++)
  14.             for(int j=1;j<n;j++)
  15.                 dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);
  16.         return dp[m-1][n-1];
  17.     }

九、地下城游戏

174. 地下城游戏 - 力扣（LeetCode）

思路

此处我们会先想到计算出最小的值，但是此处要的是最小的初始健康点数，其实也就是最小的负数的绝对值。

所以我们对于元素应该采用相减，而不是相加。

但又值得注意的是，若是最后一步到了正数，那我们需要的健康点数至少为1。

所以我们需要转换思路，从结尾到开始处的最小距离，如果点数<=0，那么就说明到此处位置的点数超出了，就不需要这么多，那么就重置为1。

代码

  1. int calculateMinimumHP(vector<vector<int>>& dungeon) {
  2.         //转换思路，从右下角到左上角的最小消耗距离，负数为加，正数为减
  3.         //从后往前,可以看做是一个累积生命值的过程
  4.         //那么就是，若生命到了0以下，说明正能量球给的足够多了，到此处的生命值只需要1即可
  5.         int m=dungeon.size(),n=dungeon[0].size();
  6.         vector<vector<int>> dp(m,vector<int>(n));
  7.         dp[m-1][n-1]=-dungeon[m-1][n-1]+1;//直接定义最后一个位置的
  8.         if(dp[m-1][n-1]<=0) //说明最后一个位置为正数，那么到此处的生命值只需要1
  9.             dp[m-1][n-1]=1;
  10.         //定义最后一列
  11.         for(int i=n-2;i>=0;i--)
  12.         {
  13.             int ret=dp[m-1][i+1]-dungeon[m-1][i];
  14.             if(ret<=0){
  15.                 ret=1;
  16.             }
  17.             dp[m-1][i]=ret;
  18.         }
  19.         for(int j=m-2;j>=0;j--)
  20.         {
  21.             int ret=dp[j+1][n-1]-dungeon[j][n-1];
  22.             if(ret<=0){
  23.                 ret=1;
  24.             }
  25.             dp[j][n-1]=ret;
  26.         }
  27.         for(int i=m-2;i>=0;i--)
  28.         {
  29.             for(int j=n-2;j>=0;j--)
  30.             {
  31.                 int life1=dp[i+1][j]-dungeon[i][j];
  32.                 int life2=dp[i][j+1]-dungeon[i][j];
  33.                 if(life1<=0||life2<=0)//两个中有一个大于0，那么就可以把这个定为1，因为要找最小的路径,那么经过的正能量球也要适当的多
  34.                 {
  35.                     dp[i][j]=1;
  36.                 }
  37.                 else
  38.                 {
  39.                     dp[i][j]=min(life1,life2);//或者给一个两个之中一个较小的
  40.                 }
  41.             }
  42.         }
  43.         return dp[0][0];
  44.     }

双表动态规划

十、按摩师

面试题 17.16. 按摩师 - 力扣（LeetCode）

思路

双表动态规划，往往会涉及到"拿"和"不拿"两个选择，那我们就需要定义两个表，分别表示不同状态下，同一位置的不同情况。

而且我们要对数字进行初始化 f[0]表示服务第一个客人获得的点数，所以

就是f[0]=nums[0],g[0]=0

代码

  1. int massage(vector<int>& nums) {
  2.         int len=nums.size();
  3.         if(len==0)
  4.             return 0;
  5.         vector<int> g(len);
  6.         auto f=g;
  7.         g[0]=nums[0],f[0]=0;//若第一个接受，那么就是第一个元素，若不接受就是0
  8.         for(int i=1;i<len;i++)
  9.         {
  10.             g[i]=f[i-1]+nums[i];
  11.             f[i]=max(f[i-1],g[i-1]);//不接受就不加上当前的数字
  12.         }
  13.         return max(f[len-1],g[len-1]);
  14.     }

十一、打家劫舍

198. 打家劫舍 - 力扣（LeetCode）

思路

思路其实同按摩师，就是不能相邻的进行盗窃，代码相同，但是这个思路需要记住，以后还会有用到

代码

  1. int rob(vector<int>& nums) {
  2.         int n=nums.size();
  3.         vector<int> f(n);
  4.         vector<int> h(n);
  5.         f[0]=nums[0],h[0]=0;
  6.         for(int i=1;i<n;i++)
  7.         {
  8.             f[i]=h[i-1]+nums[i];
  9.             h[i]=max(f[i-1],h[i-1]);
  10.         }
  11.         return max(f[n-1],h[n-1]);
  12.     }

十二、删除并且获得点数

740. 删除并获得点数 - 力扣（LeetCode）

思路

其实就是打家劫舍的升级版，删除一个数据后，那么其相邻的元素都会被删除。

而且删除同一个数据后，就会连续进行删除，所以需要一个哈希表来记录每个数据出现个数的总和

代码

  1. int deleteAndEarn(vector<int>& nums) {
  2.         int hash[100001]={0};
  3.         const int N=100001;
  4.         int len=nums.size();
  5.         for(auto e:nums)
  6.         {
  7.             hash[e]+=e;//统计每个数出现的总和——哈希表
  8.         }
  9.         vector<int> f(N);
  10.         auto g=f;
  11.         for(int i=1;i<N;i++)
  12.         {
  13.             f[i]=g[i-1]+hash[i];
  14.             g[i]=max(g[i-1],f[i-1]);
  15.         }
  16.         return max(f[N-1],g[N-1]);
  17.     }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/136818
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号