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


  • 0
    X
    public int rob(int[] nums) {
        if (nums.length==0)
            return 0;
        return rob(nums.length-1,nums);
    }
    public int rob(int i,int[] nums){
         if(i==0){
            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]);
          }
     }
    //d(n)=max(d(n-1),d(n-2)+v(n))
    //d(1)=v(1),d(2)=max(v(1),v(2))

  • 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.