程序开发多少钱/关键词seo

LeetCode.198. 打家劫舍

难度：medium

动态规划的方法，注释写的很清楚，要注意的是nums只有一个元素的特殊情况；

Java： 

class Solution {public int rob(int[] nums) {int length = nums.length;//dp[i]为盗窃前i号房屋所能偷窃到的最高金额int[] dp = new int[length + 1]; if (length <= 1) {return nums[0];}//初始化dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);//dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])for (int i = 2; i < length; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[length - 1];}
}

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)