首页 > 其他 > 详细

动态规划LeetCode198打家劫舍

时间:2019-06-17 22:57:43      阅读:173      评论:0      收藏:0      [点我收藏+]

动态规划(DP)要多做题,字符串上的dp和树形dp都比较难,但是不常考,最常考的还是数组上的dp题目。

写DP题目时最关键的还是要想到用dp这种方法。动态规划题目一般暴力枚举都可以解决,但是暴力时间复杂度一般都比较大,那么就要想到贪心和动态规划。

 

LeetCode198 打家劫舍

题目描述:

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
  偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
  偷窃到的最高金额 = 2 + 9 + 1 = 12 。

分析:

技术分享图片

技术分享图片

 1 class Solution {
 2     public int rob(int[] nums) {
 3         if(nums.length==0) {
 4             return 0;
 5         }
 6         if(nums.length==1) {
 7             return nums[0];
 8         }
 9         int[] dp=new int[nums.length];
10         dp[0]=nums[0];
11         dp[1]=Math.max(nums[0],nums[1]);
12         for(int i=2;i<nums.length;i++) {
13             dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
14         }
15         return dp[nums.length-1];  
16     }
17 }

技术分享图片

欢迎评论!!共同进步!!

动态规划LeetCode198打家劫舍

原文:https://www.cnblogs.com/hengzhezou/p/11042414.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!