链接
题目：
思路一：动态规划
-
dp定义：在 i 位置能抢到最多的钱是多少；
-
状态和选择
状态只有索引 i ，选择即 选择 偷 还是 不偷，哪个钱多就选哪个； -
base case：
dp[0]=nums[0]即在第一个房子时，能偷到的最多的钱就是直接偷 ！不用犹豫 ！
由于for循环中有 i-2，所以单独拎出 i=1时的情况；
class Solution {
public int rob(int[] nums) {
if(nums==null || nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
//dp定义：第i间屋子时可以偷的最多的钱
int n=nums.length;
int[] dp=new int[n];
//base case
// 到第0索引处能偷的最大即为nums[0]
dp[0]=nums[0];
dp[1]=Math.max(0+nums[1] , dp[0]);
for(int i=2;i<n;i++){
// 要么偷，即i-1不能被偷，钱是i-2和nums[i]； 不偷，则i-1被偷！
dp[i]=Math.max(dp[i-2]+nums[i] , dp[i-1]);
}
return dp[n-1];
}
}
思路二：动态规划+递归
-
dp定义：以start为起点，可以偷的最多的钱是多少, 所求即 dp(nums,0) ；
-
状态和选择：
状态：就是起点start，即小偷所处的位置即nums数组的索引；
选择：当前要么抢，要么不抢，如果不抢则start想前走+1，如果抢，则要加上当前nums中start位置的钱，然后start+2 ！ -
base case：
如果 start > nums.lenth-1 ，则为0 ，即起点超过最后一家就抢不到了； -
重叠子问题
class Solution {
int memo[];
public int rob(int[] nums) {
memo=new int[nums.length];
Arrays.fill(memo,-1); // 初始化dp
return dp(nums,0);
// memo定义：从 i出发能抢到最多的钱总数
}
int dp(int[] nums,int start){ // start就对应题目数组的索引；
// base case ，即start超过最后一间房子后，抢到的为0
if(start>=nums.length){
return 0;
}
// 重叠子问题
if(memo[start]!=-1){
return memo[start];
}
// 状态转移（选择）：不抢 or 抢
memo[start]=Math.max( dp(nums,start+1) , dp(nums,start+2)+nums[start] );
return memo[start];
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89200.html
