【刷刷刷，爽！】leetcode198. 打家劫舍

本文主要是介绍【刷刷刷，爽！】leetcode198. 打家劫舍，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目如上！
这是一道非常非常标准的初级动规题。属于走楼梯的进阶版。所以我们尝试把他变成走楼梯。
怎么变？或者说是怎么看成走楼梯。
答案是！！！！
看最后一个数。
往往会最有灵感。
比如示例1中[1,2,3,4]，最后一个是4,他后面没有数字了，很容易就会想到两种情况，“我要达成最优解，带还是不带这个数字呢？”
此时，答案的后门就敞开了。

1. 带了这个数，就要再加上隔一个数的那个数下的最优解，也就是f(n-2)+num[n]
2. 不带他玩，就只算f(n-1)
3. 最后，比较下他俩噜

然后，具体体现形式有三种，递归（可能超时），用数组记录（不是特殊情况费那劲干嘛），用俩变量记录下n-1,n-2（就这个了）

代码如下：

public class Solution {public int Rob(int[] nums) {if (nums.Length == 1) return nums[0];if (nums.Length == 2) return Math.Max(nums[0], nums[1]);int MaxResult = 0;int f1 = nums[0];int f2 = Math.Max(nums[0], nums[1]);for (int i = 2; i < nums.Length; i++){MaxResult = Math.Max(f2, (nums[i] + f1));f1 = f2;f2 = MaxResult;}return MaxResult;}
}

溜！

这篇关于【刷刷刷，爽！】leetcode198. 打家劫舍的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---