打家劫舍

描述

力扣第 198 题。你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例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 。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

思路

本题是动态规划最好的实现。从上述情景中，可以很好的理解为对一个数组元素都是正整数的数组，将里面的元素进行相加，相邻的元素不能相加，相加的元素之间只能隔一个数据，求相加的最大和。

在计算的时候，我们可以把一个大的任务划分成一个一个的小任务，被划分的大任务依赖于小任务的执行结果。比如我们需要求 F(N) [N 表示数组坐标 + 1，表示数组里面的第几个元素] 的值，那么我们可以取 F(N-1) 的值，也可以取 F(N-2) + num[N - 1] 的值。那么 F(N - 1) 和 F(N - 2) 的任务也可以继续被划分。最终我们可以得到我们想要的值。

在计算的时候，我们需要知道结束的场景，不能无限的调用下去，所以我们将第 0 个元素赋值为 0。第一个元素就是数组的第一个值，nums[0]。

在编程过程中，我们需要定义一个数组，来将已经计算好的值存储，避免重复计算。

代码具体实现

Java语言版本

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if(length == 0 ){
            return 0;
        }
        //用来记录已经计算过的数据值，防止重复计算
        int[] resultValue = new int[length + 1];
        resultValue[0] = 0;
        resultValue[1] = nums[0];
        //遍历比较，计算，获取最大值
        for(int i = 2 ; i<= length ; i ++){
            //比较获取 前一次计算的值 还是 当前值和前前一次计算的值相加的和
            int retValue =Math.max(resultValue[i - 2] + nums[i-1],resultValue[i - 1]); 
            resultValue[i] = retValue;
        }
       return resultValue[length];
    }
}

Go语言版本

func rob(nums []int) int {
        length := len(nums)
        if length == 0 {
            return 0
        }
        //用来记录已经计算过的数据值，防止重复计算
        resultValue := make([]int,length + 1)
        resultValue[0] = 0
        resultValue[1] = nums[0]
        //遍历比较，计算，获取最大值
        for i := 2 ; i<= length ; i ++ {
            //比较获取 前一次计算的值 还是 当前值和前前一次计算的值相加的和
            retValue := max(resultValue[i - 2] + nums[i-1],resultValue[i - 1])
            resultValue[i] = retValue
        }
       return resultValue[length]
}
/* 函数返回两个数的最大值 */
func max(num1, num2 int) int { 
    /* 声明局部变量 */
     var result int 
     if num1 > num2 {
          result = num1 
        } else { 
            result = num2 
        } 
    return result 
}