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)