动态规划之抢劫问题-LT213
2024-09-06 16:15:16
找到大问题和小问题之间共有的特性,列出一定的状态转移规律,然后设计满足条件的小问题解决方案,最后凭借记忆中的中间值快速求出最终解
动态规划问题的复杂性在于你永远不知道下一个题目中的状态是什么,有什么样的状态转移规律,抢劫房子的问题是一个经典的动态规划问题,是裴波那切数列问题的一种,类似于爬楼梯。。。它分为单向抢劫与环形抢劫
单向抢劫
单项抢劫的题目描述为:抢劫一排住户,但是不能抢邻近的住户,求最大抢劫量。
单向的抢劫问题还是比较简单的,我们可以定义一个dp数组,记录抢劫位置为i处时候的最大抢劫数目,代码如下:
private int[] dp; private int rob(int[] nums){
if(nums.length == 0) return 0;
if(nums.length == 1) return nums[0];
dp = new int[nums.length + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
return helper(nums, nums.length);
} private int helper(int[] nums, int n){
if(n < 0) return 0;
if(dp[n] != -1) return dp[n];
dp[n] = Math.max(helper(nums, n - 1), helper(nums, n - 2) + nums[n-1]);
return dp[n];
}
这样的做法是没问题,而且符合动态规划问题的一般思路,但是还有可以优化的地方,我们这样的解法的空间复杂度较高,通过分析题目我们可以知道dp[i]仅与前两个状态有关系,所以我们可以采取如下的方式边记边忘,这样就可以成功的把空间复杂度降低为O(1)
public int rob(int[] nums) {
int pre2 = 0, pre1 = 0;
for (int i = 0; i < nums.length; i++) {
int cur = Math.max(pre2 + nums[i], pre1);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
环形抢劫
环形抢劫又变了!第一个房子和最后一个房子成了邻居,所以我们就不可以同时把他们两家一块儿抢了了,但是细细一想,既然不能同时抢劫,那么把它分成0到numSize-2和1到numSize-1不久可以了吗,保证了他们不当邻居,然后求出两者的最大值,这样我们就可以继续用单向的思路去把它解决了!
private int robII(int[] nums){
if(nums==null||nums.length==0)
return 0;
int n=nums.length;
if(n==1)
return nums[0];
return Math.max(helper(0,n-2,nums),helper(1,n-1,nums));
}
private int helper(int start, int end, int[] nums){
int[]dp=new int[end-start+2];
dp[0]=0;
dp[1]=nums[start];
for(int i=2;i<=(end-start+1);i++){
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1+start]);
}
return dp[end-start+1];
}
最新文章
- JavaScript图表FusionCharts免费在线公开课,由印度原厂技术工程师主讲,10月13日发车
- openssl创建非认证的https证书(红色的)
- 总结一下 input propertychange
- netty学习
- 柯里化/偏函数/Curring用法
- Java并发编程中的阻塞和中断
- 一些IT中的工具介绍【转】
- UVaLive 6809 Spokes Wheel (模拟)
- PHP漏洞全解(一)-PHP网站的安全性问题
- Android开发UI之Notification
- bzoj 2226: [Spoj 5971] LCMSum 数论
- discuznt学习笔记
- 电脑bios到底是什么?
- SSIS Package to Call Web Service
- 4.Java集合总结系列:Map接口及其实现
- Java集合常见面试题集锦
- 10.3 Vue 路由系统
- 记录一次有意思的XSS过滤绕过
- IDEA @Contract annotation
- java特殊字符分隔符