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

import java.util.*;


public class Solution {
   
   //f[i] 表示该位置必选时最打金额
   //g[i] 表示该位置不选时最大金额
    public int rob (int[] nums) {
        // write code here

        int n = nums.length;
        int[] f= new int [n]; //必选
        int[] g = new int [n]; //不选
        //1.初始化 必选为发nums[0]
        f[0] = nums[0];
        g[0] = 0; 

        //2.填表 1.必选时，此时的值即为g[i-1](表示i-1不选) + nums[i]。2、不选i时,就要看i-1位置选或者不选两种状态
        for(int i=1;i<n;i++ ){
            f[i] = g[i-1] +nums[i]; //必选

            //i-1位置选或者不选两种情况
            g[i] = Math.max(f[i-1],g[i-1]);
        }
    

        return Math.max(g[n-1],f[n-1]);
    }
}