Java DP solutions, recursion & iteration


  • 0
    M
    public class Solution {
        public int rob(int[] nums) {
            if(nums==null || nums.length==0) return 0;
            final int N = nums.length;
            int[] dp = new int[N];
            if(N==1) return nums[0];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0], nums[1]);
            if(N==2) return dp[1];
            // return iteration_rob(nums, dp);
            return recursion_rob(nums, dp);
        }
        
        private int recursion_rob(int[] nums, int[] dp){
            boolean allZero = true;
            for(int ele : nums){
                if(ele != 0){
                    allZero = false;
                    break;
                }
            }
            if(allZero) return 0;
            recursion(nums.length-1, nums, dp);
            int max = 0;
            for(int ele : dp){
                max = Math.max(max, ele);
            }
            return max;
        }
        private int recursion(int i, int[] nums, int[] dp){
            if(i<0) return 0;
            if(dp[i]>0) return dp[i];
            int cur = nums[i] + recursion(i-2, nums, dp);
            int pre = recursion(i-1, nums, dp);
            dp[i] = Math.max(cur, pre);
            return dp[i];
        }
        
        private int iteration_rob(int[] nums, int[] dp){
            int max = 0;
            for(int i=2; i<nums.length; i++){
                dp[i] = Math.max(nums[i]+dp[i-2], dp[i-1]);
                max = Math.max(max, dp[i]);
            }
            return max;
        }
        
    }
    

Log in to reply
 

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