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

动态规划算法集合（更新到9地下城游戏）

作者：weixin_40725706 | 2024-06-14 23:12:48

赞

踩

动态规划算法集合（更新到9地下城游戏）

目录

方法论

1.第n个泰波那契数

2.三步问题

3.使用最小花费爬楼梯

4.解码方法

5.不同路径

6.不同路径2

7.珠宝的最高价值

8.下降路径最小和

9.地下城游戏

方法论

  1. 1.状态表示
  2.  
  3. 是什么？dp表里的值所表示的含义
  4.  
  5. 怎么来？1>.题目要求
  6.  
  7.        2>题目要求+经验（这个为主要使用方法）
  8.  
  9.         3>分析问题过程中发现重复子问题
  10.  
  11. 2.状态转移方程
  12.  
  13. dp[i]代表什么？
  14.  
  15. 根据最近一步的状态表示
  16.  
  17. 3.初始化
  18.  
  19. 保证数组不越界
  20.  
  21. 4.填表顺序，保证填写该状态时，所需要的状态已经计算过了
  22.  
  23. 5.返回值
  24. 题目要求+状态表示
  25.  
  26. （6.空间优化）
  27. 可以使用轮换数组来减少空间消耗，即使用有限个变量通过一轮轮赋值来向前推进
动态规划中要弄清楚每一步是为什么，多想想为什么

1.第n个泰波那契数

  1. 1.dp[i]表示第i给泰波那契数的值（题目给定）
  2.  
  3. 2.dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
  4.  
  5. 3.将dp[0] dp[1] dp[2] 进行初始化
  6.  
  7. 4.从左向右
  1. class Solution {
  2. public:
  3.     int tribonacci(int n) 
  4.     {
  5.         if(n == 0)return 0;
  6.         if(n == 1 || n == 2)return 1;
  7.  
  8.         vector<int> dp(n+1);
  9.         dp[0] = 0;
  10.         dp[1] = 1;
  11.         dp[2] = 1;
  12.         for(int i = 3; i <= n; i++)
  13.         {
  14.             dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
  15.         }
  16.         return dp[n];
  17.     }
  18. };

2.三步问题

  1. class Solution {
  2. public:
  3.     int waysToStep(int n) 
  4.     {
  5.  
  6.         if(n <= 2)return n;
  7.         if(n == 3)return 4;
  8.         vector<int> dp(n+1);
  9.         dp[1] = 1;
  10.         dp[2] = 2;
  11.         dp[3] = 4;
  12.         for(int i = 4;i <= n; i++)
  13.         {
  14.              dp[i] = ((dp[i-1] + dp[i-2])%(1000000007) + dp[i-3])%(1000000007);
  15.         }
  16.         return dp[n];
  17.     }
  18. };

3.使用最小花费爬楼梯

  1. 1.dp[i]表示爬到i位置时使用的最小花费
  2.  
  3. 2.dp[i] = min( (dp[i-1] + cost[i - 1]), (dp[i-2] + cost[i - 2]) );
  4.  
  5. 3.将dp[1] dp[2] 进行初始化
  6.  
  7. 4.从左向右
  1. class Solution {
  2. public:
  3.     int minCostClimbingStairs(vector<int>& cost) {
  4.         int n = cost.size();
  5.         vector<int> dp(n+1);
  6.         for(int i = 2; i <= n; i++)
  7.         {
  8.             dp[i] = min( (dp[i-1] + cost[i-1]), (dp[i-2] + cost[i-2]) );
  9.         }
  10.         return dp[n];
  11.     }
  12. };

4.解码方法

  1. class Solution {
  2. public:
  3.     int numDecodings(string s) {
  4.         int size = s.size();
  5.         vector<int> dp(size);
  6.         if(s[0] == '0')return 0;
  7.  
  8.         if(s[0] > '0' && s[0] <= '9')dp[0] = 1;
  9.         if(size <= 1)return dp[size-1];
  10.  
  11.         if(s[1] > '0' && s[1] <= '9')dp[1]++;
  12.         int tmp = (s[0]-'0')*10 + s[1] - '0';
  13.         if(tmp >= 10 && tmp <= 26)dp[1]++;
  14.         if(size <= 2)return dp[size-1];
  15.  
  16.         for(int i = 2; i <= size - 1; i++)
  17.         {
  18.             if(s[i] > '0' && s[i] <= '9')dp[i] +=dp[i - 1];
  19.             tmp = (s[i-1]-'0')*10 + s[i] - '0';
  20.             if(tmp >= 10 && tmp <= 26)dp[i] += dp[i-2];
  21.         }
  22.         return dp[size-1];
  23.     }
  24. };
  1. //使用虚拟节点优化后，初始化更加方便，但是需要注意映射关系
  2. class Solution {
  3. public:
  4.     int numDecodings(string s) {
  5.         int size = s.size();
  6.         vector<int> dp(size+1);
  7.         dp[0] = 1;//dp[0]等于1是因为，在循环判断中如果s[0]能与s[1]组合，它的解码方式就是一种，就                
  8.                   //会加上dp[0]
  9.         if(s[0] == '0')return 0;
  10.         if(s[0] > '0' && s[0] <= '9')dp[1] = 1;
  11.  
  12.         for(int i = 2; i <= size; i++)
  13.         {
  14.             if(s[i - 1] > '0' && s[i - 1] <= '9')dp[i] +=dp[i - 1];
  15.             int tmp = (s[i-1 - 1]-'0')*10 + s[i - 1] - '0';//映射关系改变，i 要整体减1
  16.             if(tmp >= 10 && tmp <= 26)dp[i] += dp[i-2];
  17.         }
  18.         return dp[size];
  19.  
  20.     }
  21. };

5.不同路径

使用虚拟位置的方法来确定填表

  1. class Solution {
  2. public:
  3.     int uniquePaths(int m, int n) {
  4.         vector<vector<int>> dp(m+1,vector<int>(n+1));
  5.         dp[0][1] = 1;//因为[1][1]位置是初始位置，初始位置就算是一种情况，所以[0][1]处赋值为1
  6.         for(int i = 1;i <= m; i++)
  7.         {
  8.             for(int j = 1;j <= n; j++)
  9.             {
  10.                 dp[i][j] = dp[i][j-1] + dp[i-1][j];//下一格的路线是接在原路线上，算同一路线，所 
  11.                                                    //以其路线总数就是左一格和上一格的路线之和
  12.             }
  13.         }
  14.         return dp[m][n];
  15.     }
  16. };

6.不同路径2

  1. class Solution {
  2. public:
  3.     int uniquePathsWithObstacles(vector<vector<int>>& ob) {
  4.         int m = ob.size();
  5.         int n = ob[0].size();
  6.         vector<vector<int>> dp(m+1,vector<int>(n+1));
  7.         dp[0][1] = 1;
  8.         for(int i = 1;i <= m; i++)
  9.         {
  10.             for(int j = 1;j <= n; j++)
  11.             {
  12.                 if(ob[i-1][j-1] == 0)//主要思路同上，增加障碍物的判断
  13.                 dp[i][j] = dp[i][j-1] + dp[i-1][j];
  14.                 else dp[i][j] = 0;
  15.             }
  16.         }
  17.         return dp[m][n];
  18.     }
  19. };

7.珠宝的最高价值

  1. class Solution {
  2. public:
  3.     int jewelleryValue(vector<vector<int>>& fm) {
  4.         int m = fm.size();
  5.         int n = fm[0].size();
  6.         vector<vector<int>> dp(m+1,vector<int>(n+1));
  7.         for(int i = 1; i <= m; i++)
  8.         {
  9.             for(int j =1;j <= n; j++)
  10.             {
  11.                 dp[i][j] = max(dp[i-1][j],dp[i][j-1])+fm[i-1][j-1];//每次走之前选价值更大的， 
  12.                                                                    //其它同上面的题目
  13.             }
  14.         }
  15.         return dp[m][n];
  16.     }
  17. };

8.下降路径最小和

  1. 1.状态表示
  2. 下降到[i][j]的最小路径和
  3. 2.状态转移方程
  4. 前一行三个中位置的最小路径和+本位置的路径长度
  5. 3.初始化
  6. 先把全部位置初始化为INT_MAX，选择最小值时就不会影响到选值
  7. 把第一行初始化为0，计算第一行时初始值就是该位置的路径长度
  8. 4.填表顺序 
  9. 从上到下从左到右
  10. 5.返回值 最后一行最小的
  1. class Solution {
  2. public:
  3.     int minFallingPathSum(vector<vector<int>>& ma) {
  4.         int m = ma.size()+ 1;
  5.         int n = ma.size()+2;
  6.         vector<vector<int>> dp(m,vector<int>(n,INT_MAX));
  7.         for(int j = 0; j < n; j++)
  8.         {
  9.             dp[0][j] = 0;
  10.         }
  11.         for(int i = 1; i < m; i++)
  12.         {
  13.             for(int j = 1; j < n - 1; j++)
  14.             {
  15.                 dp[i][j] = min(dp[i-1][j], min(dp[i - 1][j-1],dp[i-1][j+1]))+ ma[i-1][j-1];
  16.             }
  17.         }
  18.         int tmp = INT_MAX;
  19.         for(int j = 1; j < n -1; j++)
  20.         {
  21.             tmp = min(tmp,dp[m-1][j]);
  22.         }
  23.         return tmp;
  24.     }
  25. };

9.地下城游戏

  1. 1.状态表示
  2. dp[i][j]位置处到达终点所需要的最低健康点数，此处作为起点
  3. 如果某处作为终点，那么因为该处接受所需的健康点数与从该处出去之后所增加或减少的健康点数有关，因此不能依靠前一步确定这一步
  4. 2.状态转移方程
  5. dp[i][j] + dg[i][j] >= dp[i][j+1]  或
  6. dp[i][j] + dg[i][j] >= dp[i+1][j]  
  7. 某一个位置到结束时后所需要的最低健康点数+此处的所得的健康点数（可能为负数） 要大于等于下一个位置到结束后需要的最低健康点数。取最小的值
  8. （终点实际上是右下角格子再向右或者向下一格，因为这个格子也有增加以及减少健康的判定）
  9. 如果某个地方提供的健康值很大，那么会出现即使通过这个地方之前勇士的健康值为负数他依旧可以顺利通过，但显然是不符合题意的，所以dp[i][j]>= 1,每次要与1取大
  10. 3.初始化
  11. 先把全部位置初始化为INT_MAX，选择最小值时就不会影响到选值
  12. 把右下角格子的右边以及下面的位置初始化为1，脱离右下角格字结束时最小的健康值为1，要保证勇士存活
  13. 4.填表顺序 
  14. 从下到上从右到左
  15. 5.返回值dp[0][0]

 

  1. class Solution {
  2. public:
  3.     int calculateMinimumHP(vector<vector<int>>& dg) {
  4.         int m = dg.size();
  5.         int n = dg[0].size();
  6.         vector<vector<int>> dp(m+1,vector<int>(n+1, INT_MAX));
  7.         dp[m][n-1] = 1;
  8.         dp[m-1][n] = 1;
  9.         for(int i = m - 1; i >=0; i--)
  10.         {
  11.             for(int j = n - 1; j >=0;j--)
  12.             {
  13.                 dp[i][j] = min(dp[i][j+1], dp[i+1][j]) - dg[i][j];
  14.                 dp[i][j] = max(1,dp[i][j]);
  15.             }
  16.         }
  17.         return dp[0][0];
  18.     }
  19. };

 

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

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

  

闽ICP备14008679号