# C# code get TLE

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

• 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];
}
}
``````

• thanks a lot!

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