LeetCode-动态规划-213. 打家劫舍 II
2021/10/12 23:14:10
本文主要是介绍LeetCode-动态规划-213. 打家劫舍 II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
213. 打家劫舍 II
思路:考虑三种情况注释代码中
class Solution { public: int rob(vector<int>& nums) { if(nums.empty()) return 0; if(nums.size()==1) return nums[0]; //考虑首端,不考虑尾端 int value1 = robrange(nums,0,nums.size()-2); //考虑尾端,不考虑首端 int value2 = robrange(nums,1,nums.size()-1); return max(value1,value2); } //考虑以下三种情况 //1:不考虑首尾的情况 //2:考虑首端情况 //3:考虑尾端情况 //由于情况1包含在情况2,3中,所以只要考虑后面两个即可 int robrange(vector<int>& nums,int start,int end){ if (end == start) return nums[start]; vector<int> dp(nums.size(),0); //第i个房间最高金额是dp[i] dp[start] = nums[start]; dp[start+1] = max(nums[start],nums[start+1]); for(int i=start+2;i<=end;i++){ dp[i] = max(nums[i]+dp[i-2],dp[i-1]); } return dp[end]; } };
这篇关于LeetCode-动态规划-213. 打家劫舍 II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享