I think my solution was DP, But I really don't understand why it is time limit exceeded

  • 0
    public int rob(int[] nums) {
        if (nums.length==0)
            return 0;
        return rob(nums.length-1,nums);
    public int rob(int i,int[] nums){
            return nums[0];
         } else if(i==1){
            return Math.max(nums[0],nums[1]);
         } else{
          return Math.max(rob(i-1,nums),rob(i-2,nums)+nums[i]);

  • 0


  • 2

    This is certainly not DP. This is just a recursive solution. DP implies saving smaller results to reuse them for getting bigger results. You just re-calculate them instead, which leads to exponential complexity.

    To make it DP you have to either memoize results in your solution (top-down DP) or use iterative bottom-up approach.

Log in to reply

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