赞
踩
1.找出重复无后效性的子问题
2.找出状态转移方程
2.初始值,确定dp数组的维度以及要保存的内容是什么以及dp[0]的值
动态规划定义
动态规划–:Dynamic programming,简称 DP,是一种可以将将原问题分解成一个个小问题求解的过程。动态规划需要保存子问题的结果,然后根据子问题的结果递推更大的问题,这种是自底向上解法;另一种是自顶向下解法,采用递归函数向下求解。
动态规划往往使用在有递归子问题或者最优子结构类型的题目,动态规划中最难的就是找到递推子式,也就是从子问题递推最终问题的过程。
动态规划应满足:
「有向无环图」「拓扑序」表示了每一个子问题只求解一次,以后求解问题的过程不会修改以前求解的子问题的结果;
换句话说:如果之前的阶段求解的子问题的结果包含了一些不确定的信息,导致了后面的阶段求解的子问题无法得到,或者很难得到,这叫「有后效性」,我们在当前这个问题第 1 次拆分的子问题就是「有后效性」的(大家可以再翻到上面再看看);
解决「有后效性」的办法是固定住需要分类讨论的地方,记录下更多的结果。在代码层面上表现为:
状态数组增加维度,例如:「力扣」的股票系列问题;
把状态定义得更细致、准确,例如:前天推送的第 124 题:状态定义只解决路径来自左右子树的其中一个子树。
解题模板
这种就是典型的采用递归函数的类型题,常见的比如:树的遍历、斐波那契数列求解。
1.声明递归函数,以及声明保存中间结果的容器
2.确定递归公式—往往就是递归函数的结合
3.确定终止条件–这一步也很重要,否则程序将不会停止
4.在递归函数中,要用到保存下来的中间结果
自底向上式是动态规划
1.分析子问题结构
2.得到递推公式
3.声明保存中间结果的容器
4.使用循环结构,从最小子问题向上求解
常见题型
1.线性动态规划
也就是是在线性数据,如数组上进行求解,其目标函数是由多个线性不等式决定,,结果是求出目标函数的最大值或者最小值。
这类问题往往需要两个循环,第一个循环为动态规划所必须的,自底向上;第二个循环是对于当前n,要判断0-n-1之间,n加入哪一个会更优。
这类问题既是对每一个当前n都要考虑之前的所有状态,而不单单是n-1状态。
常见问题:最长递增子序列
2.区间动态规划
区间动态规划意思就是求解区间i–j的最优值,而大区间的最优值为两个小区间的最优值合并得来。
区间动态规划的 模板为:
for (int len=2;len<=n;len++)
for (int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
for (int k=i;k<=j;k++)
f[i][j]=max/min(f[i][j],f[i][k]+f[k][j]+something)
}
常见题目:合并石子堆
3.前缀和动态规划
前缀和是容器中保存的是从0-i之间的最优解,,那么i+1状态的解就可以通过i状态解计算得出。
既不保存区间的结果,保存的是前缀的结果
多用在字符串题目上
力扣原题
p55 跳跃游戏
class Solution { public boolean canJump(int[] nums) { int n=1; for(int i=nums.length-2;i>=0;i--){ if(nums[i]>=n) { n=1; } else { n++; } if(i==0&&n>1) { return false; } } return true; } }
p45 跳跃游戏2
// class Solution { // public int jump(int[] nums) { // //dp数组保存从初始位置跳到该位置所用的最小步长。 // ///递推公式dp[i] = min(dp[j]+1) if j + nums[j] >= i, 0<=j<i // ///优化:j的左区间不能到0,应该设置一个数left.对于当前i,left到不了,那么i+1处left肯定也到不了 // int[] dp = new int[nums.length]; // int left = 0,tag=0; //保存左区间 // Arrays.fill(dp,nums.length); // dp[0] = 0; // if(nums.length<=1) // return 0; // for(int i=1;i<nums.length;i++){ // tag=0; // for(int j=left;j<i;j++){ // if(j+nums[j]<i ){ // if(tag==0) // left=j; // } // else{ // tag=1; // if(dp[i]>dp[j]+1) // dp[i] = dp[j]+1; // } // } // // for(int j=i-1;j>=left;j--){ // // if((j+nums[j]>=i) && dp[i]>dp[j]+1) // // dp[i] = dp[j] + 1; // // } // } // return dp[nums.length-1]; // } // } class Solution { public int jump(int[] nums) { if (nums == null || nums.length == 0 || nums.length == 1) { return 0; } //记录跳跃的次数 int count=0; //当前的覆盖最大区域 int curDistance = 0; //最大的覆盖区域 int maxDistance = 0; for (int i = 0; i < nums.length; i++) { //在可覆盖区域内更新最大的覆盖区域 maxDistance = Math.max(maxDistance,i+nums[i]); //说明当前一步,再跳一步就到达了末尾 if (maxDistance>=nums.length-1){ count++; break; } //走到当前覆盖的最大区域时,更新下一步可达的最大区域 if (i==curDistance){ curDistance = maxDistance; count++; } } return count; } }
p62 不同路径
下面这题展示了动态规划的问题通用解法
1.找出无后效性的子问题-即当前状态结果一旦确定就不会受到之后状态的影响
2.推导递推公式,是核心代码
3.确定dp数组及其初始化
class Solution { public int uniquePaths(int m, int n) { //子问题:到达dp[i][j]一共有几条路。无后效性的子问题 //递推公式:dp[i][j] = dp[i-1][j]+ dp[i][j-1] if i-1>=0&&j-1>=0 //else dp[i][j] = dp[i-1][j] or dp[i][j-1] 自能从左边或上面下来 //初始化dp[0][0]=0 int[][] dp = new int[m][n]; dp[0][0]=1; if(m==1 || n==1) return 1; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i-1>= 0 && j-1 >=0) dp[i][j] = dp[i-1][j] + dp[i][j-1] ; else if(i-1>=0) dp[i][j] = dp[i-1][j]; else if(j-1>=0) dp[i][j] = dp[i][j-1]; } } return dp[m-1][n-1]; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。