打家劫舍

198. 打家劫舍

leetcode 链接

思路：

动态规划

1.确定 dp 数组含义：dp[i] 表示偷窃第 i 间房屋时，能够偷窃到最高的金额为 dp[i]。

2.确定初始值：dp[0] = nums[0], dp[1] = Math.max(nums[0], nums[1])。

3.确定遍历方向：从前往后遍历。

4.确定转换方程：面对第 i 间房屋时有两种选择，偷或者不偷。偷的话，则前一间不能偷，只能用前两间的金额加上当前房屋的金额。不偷的话，则最大金额为上一间房屋的金额。两者取最大值即可。

5.确定结束条件：遍历到最后一间房屋，返回 dp[length - 1]即可。

typescript 解法

function rob(nums: number[]): number {
  // 确定dp数组，dp表示偷窃第i间房屋时，能够偷窃到最高的金额为dp[i]
  const length: number = nums.length;
  const dp: number[] = new Array(length).fill(0);
  if (length == 1) {
    return nums[0];
  }
  // 初始化dp数组
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  // 确定遍历方向，从前往后
  for (let i = 2; i < length; i++) {
    // 确定转换方程,面对第i间房屋时有两种选择，偷或者不偷。
    // 偷的话，则前一间不能偷，只能用前两间的金额加上当前房屋的金额。
    // 不偷的话，则最大金额为上一间房屋的金额。两者取最大值即可。
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  }
  return dp[length - 1];
}

go 解法

func rob(nums []int) int {
    // dp[i] 表示偷窃第i号房屋时，能偷窃到的最高金额
    length := len(nums)
    dp := make([]int, length)
    if length < 2 {
        return nums[0]
    }
    // 初始化dp数组
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    // 确定遍历方向
    for i := 2; i < length; i ++ {
        // 确定转换方程，取dp[i - 2] + nums[i], dp[i - 1] 两者最大值
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
    }
    return dp[length - 1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}