198.打家劫舍

题目描述

题解

动态规划

状态定义

使用一个一维数组dp[i]来表示第i天所能获得的最大金额.

状态转移方程

对每一天的选择进行分析, 要么抢要么不抢两种选择

如果抢了:

dp[i] = nums[i] + dp[i-2]

如果不抢:

dp[i] = dp[i-1]

初始化

dp[0] = 0, 表示第零天能够抢到的金额为0

public int rob(int[] nums) {
    int len = nums.length;
    if (len == 0) {
        return 0;
    }

    int[] dp = new int[len + 1];
    dp[0] = 0;
    dp[1] = nums[0];

    for (int i = 2; i <= len; i++) {
        dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);
    }

    return dp[len];
}