题解 | #打家劫舍(一)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        // write code here
        // 状态定义dp[i]：表示长度为i的数组，最多能偷取多少钱
        int dp[] = new int[nums.length + 1];
        // 初始化：长度为1只能偷第一家
        dp[1] = nums[0];
        // 遍历状态转移
        for(int i = 2; i <= nums.length;i++){
            // 转移方程：dp[i - 1]表示偷上家不偷当前这家；nums[i - 1]+dp[i - 2]表示偷当前这家，不偷上家，金额与上上家相加。
            dp[i] = Math.max(dp[i - 1],nums[i - 1]+dp[i - 2]);
        }
        return dp[nums.length];
    }
}