Java easy to understand DP recursive solution


  • 1
    A
    public int rob(int[] nums) {
        if(nums.length <= 1) return nums.length == 1 ? nums[0] : 0;
        int[] dp = new int[nums.length]; Arrays.fill(dp, -1);
        return Math.max(robdp(nums, 0, dp), robdp(nums, 1, dp));
    }
    
    public int robdp(int[] nums, int prev, int[] dp){
        if(dp[prev] != -1) return dp[prev];
        
        int choice = nums[prev];
        for(int j = prev + 2; j < nums.length; j++){
            choice = Math.max(choice, robdp(nums, j, dp) + nums[prev]) ;
        }
        
        dp[prev] = choice;
        return choice;
    
    }

  • -1
    W

    share my c++ dp solution,easy to understand

    enter code here
    class Solution {
    

    public:
    int rob(vector<int>& nums) {
    int bestpre=0,bestppre=0;
    int bestnow=0;
    int i=0;
    while(i<nums.size())
    {
    bestnow=max(nums[i++]+bestppre,bestpre);
    bestppre=bestpre;
    bestpre=bestnow;
    }
    return bestnow;
    }
    };

    enter code here

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.