C# code get TLE


  • 0
    P
    public class Solution {
        public int Rob(int[] nums) {
            return GetMoney(nums,0);
        }
        
        public int GetMoney(int[] nums,int pos){
            if(pos>=nums.Length)
                return 0;
            int choose =  GetMoney(nums,pos+2) + nums[pos];
            int unchoose = GetMoney(nums,pos+1);
            
            return choose > unchoose ? choose:unchoose;
        }
    }
    

    get TLE ,how to improve my code,thanks


  • 1
    L

    This recursive method indeed runs in exponential time. Why? Let f(n) denote the recurrence of the runtime. Then f(n) = f(n - 1) + f(n - 2) + c, which is similar to the Fibonacci sequence.

    To do better, just use a table to memorize all the terms computed so far, and in this way, the runtime is improved to linear.

    public class Solution {
    	int[] f;
    
    	public int Rob(int[] nums) {
    		f = new int[nums.length];
    		Arrays.fill(f, -1);
    		return GetMoney(nums,0);
    	}
    
    	public int GetMoney(int[] nums,int pos){
    		if(pos>=nums.Length) return 0;
    		if (f[pos] != -1) return f[pos];
    
    		int choose =  GetMoney(nums,pos+2) + nums[pos];
    		int unchoose = GetMoney(nums,pos+1);
    
    		f[pos] = choose > unchoose ? choose:unchoose;
    		return f[pos];
    	}
    }
    

  • 0
    P

    thanks a lot!


Log in to reply
 

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