# Why my DP solution Time Limit Exceed

• ``````  int rob(vector<int>& nums) {

int n = nums.size();
if (n == 0)
return 0;

return max_with_edge(nums, n);

}

int max_with_edge(vector<int>& nums, int n) {

if (n == 1)
return nums.at(0);
else if (n == 2)
return nums.at(1);

return max(max_with_edge(nums, n-1), max_with_edge(nums, n - 2) + nums.at(n - 1));

}
``````

This DP solution shouldn't take too long, but got a TLE

• This is not a DP! This is a Brutal Recursion!
The time complexity is T(n), and T(n) = T(n-2) + T(n-1),

if you are familiar with fibonacci sequence recursion algorithm analysis, you should know that T(n) = O(2^n)
it's slow because you are calculating some subproblem repeatedly.

Take a look at http://functionspace.org/articles/32/Fibonacci-series-and-Dynamic-programming
And you will know whey your solution is slow.

Furthermore, it seems that you have a confusion with DP & Pure Recursion.
Basically, DP = recursion + memoization. Try doing some research : http://www.quora.com/What-is-the-difference-between-dynamic-programming-and-recursion

To make your code a DP solution, you can write as followed:

``````int rob(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
if(n == 1) return nums[0];
int * dp = new int[n + 1];
dp[0] = 0;
dp[1] = nums[0];
for(int i = 2; i <= n; i ++) {
dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);
}
return dp[n];
}
``````

The time is O(n). Although I don't use recursion, the formula in the loop still reflect the
dependency of the subproblem you defined in your recursion code. And
my code avoids repeat calculation.

If you want to write a solution based on your recursion code, you can try
lazy dynamic programming(pure memoization), which writes in recursion
but still O(n)

• I changed my code and used a similar solution to yours and it passed. I still have two questions:

1. I used a table with size n instead of size n+1. While your dp[] is size n+1 ?
2. Do you have a solution that is recursive & DP?
Thanks!

1. This is a very good question. And I think every people using DP might have the same though. The answer is: DON'T care about the table. Table is just a place to cache your
calculated result. Actually, it can be a table or even a tree. What matters is: how do you define the meaning of each entry in the table(or other data structure). In my solution, I define: dp[n] means the greatest money the robber can rob from house 0..n-1. However, in
your table, you define dp[n] means the greatest money the robber can rob from house 0..n. Therefore, my table has to be one more than the number of houses. The advantage of my design is we can define dp[0] = 0(the base case of the recursion, just makes the solution neater)
2.Yes, and here is the code

public class Solution {

``````private int [] dp;

public int rec(int n, int [] num) {

if(n == 0) return 0;

if(n == 1) return num[0];

if(dp[n] != -1) return dp[n];

dp[n] = Math.max(rec(n-1, num), rec(n-2, num) + num[n-1]);

return dp[n];
}

public int rob(int[] num) {

dp = new int[num.length+1];

for(int i = 0; i < num.length+1; i ++) dp[i] = -1;

return rec(num.length, num);

}
``````

}

• Many thanks!
I was thinking a global table variable is required...

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