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

详细动态规划-一维二维力扣例题

作者：繁依Fanyi0 | 2024-06-12 21:47:58

赞

踩

详细动态规划-一维二维力扣例题

动态规划思路：

1、定义子问题

原问题可由子问题解出来，子问题可有其他子问题解出来“最优子结构”

2、数组的含义

eg:dp[i]表示什么样的子问题的结果

3、计算顺序/状态转移方程

判断到某一个子问题，只有两种可能，要或不要（例如背包问题），动态规划计算顺序有：

-自顶向下，备忘录；

-自底向上，使用dp数组（大部分）

-自底向上（Bottom-up）方法是从‘问题的最小规模’开始，逐步解决较大规模的子问题，直到解决整个问题。这种方法通常使用迭代的方式，将子问题的解保存起来，以供后续使用。自底向上方法的优点是避免了重复计算，因为每个子问题只计算一次。典型的例子是斐波那契数列的计算，可以从最小的斐波那契数开始，逐步计算得到较大的斐波那契数。

-自顶向下（Top-down）方法是从‘问题的整体’出发，将问题分解为较小的子问题，然后递归地解决这些子问题，直到解决最小规模的子问题。这种方法通常使用递归的方式，每次解决一个子问题时，如果该子问题的解已经计算过，则直接使用已经计算的结果。自顶向下方法的优点是可以更直观地理解问题的结构和解决思路，但可能存在重复计算的问题。利用自顶向下的方法解决背包问题，可以通过递归的方式从整体问题开始，将问题划分为较小的子问题。在每个子问题中，可以选择放入当前物品或者不放入当前物品，然后递归地解决剩余的容量和剩余的物品。为了避免重复计算，可以使用一个记忆化数组来保存已经计算过的子问题的解。

状态转移，即子问题之间的递推关系【例如背包问题中Max(money[i]+res[i-1][w-weight[i]]，res[i-1][w]);能装得下当前物品，就考虑是装还是不装，比较装和bu'zhuabuzhua那个情况下的值】

目的：利用历史记录，避免重复计算：历史记录存放：一维二维数组；

4、空间优化

存在存放历史数据的数组部分数据到后面都不会再用了，造成空间浪费；

例如计算f(n)的时候只用到了f(n-1)和f(n-2)因而只需要两个变量，不断更迭改变存放子问题的解即可。

思路：

1、数组元素的含义？dp[i]

//注意，含义不同，遍历的时候界限也就可能不同

2、数组元素之间的关系式

例如：台阶问题中：d[n]=d[n-1]+d[n-2];

3、找初始值【不能分解的最小的问题】

d[1]=1,d[2]=2【初值要找齐全：不能根据公式2计算出来的都是初值】

例子：

1、二维存储leetcode64题最小路径和

分析：

 //1、数组存储的含义

d[i][j]存储从（0，0）到（i，j）的数字和[包括grid[i,j]]

  //2、数组元素之间的关系

只能从从左/右来：选择两个里面最小的

d[i][j]=Math.min(d[i-1][j],d[i][j-1])+grid[i][j];  

  //3、找初始值，不能分解的最小问题

一直向右走/向下走；无需判断

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         int m=grid.length;
  4.         int n=grid[0].length;
  5.         if(m<=0||n<=0)
  6.         {
  7.             return 0;
  8.         }
  9.        // int result=0;
  10.         //1、数组存储的含义
  11.         //2、数组元素之间的关系
  12.         //3、找初始值，不能分解的最小问题
  13.         int[][] d=new int[m][n];//存储含义：记录最小和
  14.         //result=(d[i-1][j]<d[i][j-1])?d[i-1]+grid[i][j]:d[i][j-1]+grid;
  15.         //d[i][j]=result;
  16.         //3、初始值
  17.         d[0][0]=grid[0][0];
  18.         for(int i=1;i<m;i++)
  19.         {
  20.              d[i][0]=d[i-1][0]+grid[i][0];
  21.         }
  22.         for(int j=1;j<n;j++)
  23.         {
  24.             d[0][j]=d[0][j-1]+grid[0][j];
  25.         }
  26.         for(int i=1;i<m;i++)
  27.         {
  28.             for(int j=1;j<n;j++)
  29.             {
  30.                     d[i][j]=Math.min(d[i-1][j],d[i][j-1])+grid[i][j];                
  31.             }
  32.         }
  33.         return d[m-1][n-1];
  34.  
  35.     }
  36. }
2、leetcode198 打家劫舍
  • 思路

1、存储历史记录

一维数组d[i]存储直至当前房屋的金额总数

2、数组元素之间的关系

当前房屋i的金额等于max(房屋i-2,i-3)+i房屋放的金额；

3、最小问题解

d[0]=0;

d[1]=nums[0];

d[2]=max(nums[0],nums[1]);

  1. class Solution {
  2. public:
  3.     int rob(vector<int>& nums) {
  4.         int d[nums.size()];//直至走到该房屋偷取的最大金额
  5.         d[0]=nums[0];
  6.         if(nums.size()==0)
  7.         return 0;
  8.         else if(nums.size()==1)
  9.         {
  10.             return nums[0];
  11.         }
  12.         else if(nums.size()==2)
  13.             return max(nums[0],nums[1]);
  14.         else 
  15.         {
  16.             //子问题
  17.             d[1]=nums[1];
  18.             d[2]=nums[0]+nums[2];
  19.             int i;
  20.             for(i=3;i<nums.size();i++)
  21.             {
  22.                 //元素之间的关系
  23.                 d[i]=max(d[i-2],d[i-3])+nums[i];
  24.             }
  25.             return max(d[i-1],d[i-2]);
  26.         }
  27.     }
  28. };

这里注意得判断数组大小；

应用vector:

思路二：

  1. class solution{
  2. public:
  3.     int rob(vector<int>& nums) {
  4.         if (nums.empty())//可以用vector的函数！！
  5.          {
  6.             return 0;
  7.         }
  8.         int size = nums.size();
  9.         if (size == 1) {
  10.             return nums[0];
  11.         }
  12.         vector<int> dp = vector<int>(size, 0);//
  13.         dp[0] = nums[0];
  14.         dp[1] = max(nums[0], nums[1]);
  15.         for (int i = 2; i < size; i++) {
  16.             dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);//不同的思路：当前i等于max(i-1，i-2+当前nums.i)
  17. }
  18.         return dp[i-1];
  19. }
  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         if(nums.length==0)
  4.         {
  5.             return 0;
  6.         }
  7.         int pre=0;//没有房子
  8.         int cur=nums[0];//只有一家，偷了
  9.         int len=nums.length;
  10.         for(int k=1;k<len;k++)//从第二家房子开始考虑
  11.         {
  12.            int temp=Math.max(cur,pre+nums[k]);
  13.            pre=cur;
  14.            cur=temp;
  15.         }
  16.         return cur;//循环结束的时候，cur表示到最后一个房子偷盗的最大值；
  17.  
  18.  
  19.  
  20.     }
  21. }

3、 一维中等难度leetcode139单词拆分（全排列问题）

 思路：

1、bool d[s.size()]表示字符串的长度为s.size()时，能否被列表中的字符串拼接起来

2、遍历字符串，长度为i的字符串，当列表中存在长度为j的元素，满足i>=j时，说明i长度的字符串可能被拼接，所以要进一步考虑能够拼接成功，所以，去遍历列表，存在长度为j的元素(i>=j)且元素j=s.substr(i-j,j);同时s[0:i-j-1]部分也能被拼接成功的话说明d[i]=true;

即：d[i]=(d[i-j]&&s.substr(i-j,j)==elem);elem为长度为j的列表元素；

3、子问题

当字符串长度为0时，d[0]=true;

  1. class Solution {
  2. public:
  3.     bool wordBreak(string s, vector<string>& wordDict) {
  4.            //int l=wordDict.size();//元素个数
  5.            //bool d[L+1];
  6.            
  7.             int i=1;
  8.             vector<bool> d(s.size()+1,false);
  9.             d[0]=true;
  10.             //
  11.             for(int i=1;i<=s.size();i++)//背包
  12.             {
  13.                 for(string elem:wordDict)//物品
  14.                 {
  15.                     int l2=elem.size();
  16.                     if(i>=l2)//能放得下
  17.                     {
  18.                          if(d[i]=(d[i-l2]&&(s.substr(i-l2,l2)==elem)))
  19.                             {
  20.                                  d[i]=true;;//i和l2与s[j]、d[j]的关系！
  21.                                  break;//跳出内层循环
  22.                             }
  23.                     }
  24.                        
  25.                 }
  26.             }     
  27.             return d[s.size()];
  28.     }
  29. };

4、leetcode322零钱兑换

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         //子问题：寻找凑成金额为i的硬币最少数，边界问题是dp[i=0]=0;
  4.         //数组含义dp[k]金额为k。。。
  5.         //计算顺序/状态转移方程：
  6.         // dp[i]=min(dp[i],dp[i-coins[j]+1]);//i表示金额，j表示第j个硬币的金额
  7.         // 对于金额i而言，第j个金币的金额如果小于等于i则考虑要不要加入第j个金币，加入则就是去掉金额为coins[j]的情况下，放入coins[j](需要加1)，不放入的话，即dp[i]默认值是金额数+1；
  8.         int max=amount+1;
  9.         int len=coins.length;
  10.         int[] dp=new int[max];
  11.         Arrays.fill(dp,max);//int max=amount+1;：定义一个变量max，用来表示最大的金额数，这里//是amount+1，因为最多需要amount个硬币来凑成金额amount，所以将max初始化为amount+1。
  12.         dp[0]=0;
  13.         dp[0]=0;//边界子问题
  14.         for(int i=1;i<=amount;i++)//子问题：自底向上
  15.         {
  16.             for(int j=0;j<len;j++)
  17.             {
  18.                     if(coins[j]<=i)//能放得了
  19.                     {
  20.                         dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);//i>=coins[j]
  21.                     }
  22.             }
  23.         }
  24.         return (dp[amount]>amount?-1:dp[amount]);//如果dp[amount]是默认值的值，说明没有能够凑成amount的，那么就返回-1
  25.         
  26.  
  27.     }
  28. }

方法二：自顶向下/记忆化搜索思路来源：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

  1. class Solution {
  2.     int[] memo;
  3.     public int coinChange(int[] coins, int amount)
  4.     {
  5.         //记忆化搜索/自顶向下
  6.         if(coins.length==0)
  7.         {
  8.             return -1;
  9.         }
  10.         memo=new int[amount+1];//存储1->amount
  11.         return findway(coins,amount);
  12.     }
  13.     public int findway(int[] coins,int amount)
  14.     {
  15.         if(amount<0)
  16.         {
  17.             return -1;
  18.         }
  19.         if(amount==0)
  20.         {
  21.             return 0;//边界条件，当待凑金额为0的时候，需要0个硬币
  22.         }
  23.          // 记忆化的处理，memo[n]用赋予了值，就不用继续下面的循环
  24.         // 直接的返回memo[n] 的最优值
  25.         if(memo[amount]!=0)
  26.         {
  27.             return memo[amount];//
  28.         }
  29.         int min =Integer.MAX_VALUE;
  30.         for(int i=0;i<coins.length;i++)
  31.         {
  32.             int res=findway(coins,amount-coins[i]);//子问题
  33.             if(res>=0&&res<min)
  34.             {
  35.                 min=res+1;//1是加上coins[i]
  36.  
  37.             }
  38.         }
  39.         memo[amount]=(min==Integer.MAX_VALUE?-1:min);
  40.         return memo[amount];
  41.     }
  42. }

5、leetcode最长递增子序列

注意这里并不是要求连续的递增序列，要区别！

        //1、子问题dp[i]=?从第i个元素开始开始的，子串的递增最长长度;

        //2、自底向上，dp[1]=1;//起始为1的字串，最少的最长递增序列长为1

         //3、递推关系;dp[i]=max(nums[i]>nums[j]?dp[j]+1,dp[i]);

  1. class Solution {
  2.     public int lengthOfLIS(int[] nums) {
  3.         int len=nums.length;
  4.         if(len==1)
  5.             return 1;
  6.         //1、子问题dp[i]=?i从第i个元素开始开始的，子串的递增最长长度;
  7.         //2、自底向上，dp[1]=1;//起始为1的字串，最少最长递增序列长为1
  8.         //3、递推关系;dp[i]=max(nums[i]>nums[j]?dp[j]+1,dp[i]);
  9.  
  10.         int[] dp=new int[len];
  11.         int maxl=1;
  12.         for(int i=0;i<len;i++)//判断到i位置，递增序列有多长
  13.         {
  14.             dp[i]=1;//初始值//边界
  15.             
  16.             for(int j=0;j<i;j++)//从0->i，有多少递增的
  17.             {
  18.                 if(nums[i]>nums[j])
  19.                 {
  20.                     // dp[i]=dp[j]+1;//[i]>[j],说明在dp[j]的基础上多了一个递增
  21.                     // 不用担心的d[j]=0,因为j<i.
  22.                      dp[i] = Math.max(dp[i], dp[j] + 1);//注意为什么这里要加max!!
  23.                     //  [i]>[j],则对于j而言，序列加1，[i]>[j],dp[i]=dp[j]+1;
  24.                     // [i]>[j+k],则对于j+k而言，序列加1，dp[i]=dp[j+k]+1;
  25.                     // 那么到底要给dp[i]赋予那个值，那么就要进行比较，所以用max();
  26.                 }
  27.             }
  28.             maxl=Math.max(maxl,dp[i]);
  29.         }
  30.         return maxl;
  31.         // int maxl=1;
  32.         // for(int i=0;i<len-1;i++)//起始点
  33.         // {
  34.         //     dp[i]=1;//初始化边界值；
  35.         //     int base=nums[i];
  36.         //     for(int j=i+1;j<len;j++)
  37.         //     {
  38.                 
  39.         //         if(nums[j]>base)
  40.         //         {
  41.         //             dp[i]++;
  42.         //             base=nums[j];
  43.         //         }
  44.  
  45.               
  46.         //     }
  47.         //     maxl=Math.max(dp[i],maxl);
  48.         // }
  49.         // return maxl;
  50.  
  51.  
  52.     }
  53. }

 思路二：动态规划+二分查找

遍历数组里面的元素，对每一个元素用二分查找，找到一个数组里面合适的位置插入：

找到第一个>=num的位置，比所有元素都小的话，就覆盖第一个元素，比有的小，有的大，那么就覆盖掉比它大的，因为较小的元素，后面有比它大的可能才更大。

如果里面的元素都比他小，那么说明二分查找的右边指针没有动过，说明判断的num要添加到数组的后面，递增序列长度+1.

  1. class Solution {
  2.     public int lengthOfLIS(int[] nums) {
  3.         int len=nums.length;
  4.         int[] tails=new int[len];//递增数组
  5.         int res=0;
  6.         for(int num:nums)
  7.         {
  8.             int i=0,j=res;//每个元素判断
  9.             while(i<j)//二分查找：有序查找
  10.             {
  11.                 int m=(i+j)/2;//
  12.                 if(tails[m]<num)//中间的值小于当前数据
  13.                 {
  14.                     i=m+1;//向右边找，
  15.                 }
  16.                 else if(tails[m]>=num){
  17.                     j=m;//否则向左边找
  18.                 }
  19.                 // else{
  20.                 //     break;
  21.                 // }
  22.             }//i>=j跳出
  23. // 整个过程可以理解为在一个有序数组tails中查找第一个【大于等于】num的元素的位置。
  24.             tails[i]=num;
  25.             if(res==j)//说明都比目标值num小，//新序列长度+1
  26.             {
  27.                 res++;
  28.             }
  29.         }
  30.         return res;
  31.  
  32.     }
  33. }

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

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

  

闽ICP备14008679号