Why my DP solution Time Limit Exceed


  • 1
    H
      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


  • 2
    J

    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)


  • 0
    H

    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!

  • 0
    J

    for your question:

    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);
    
    }
    

    }


  • 0
    H

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


Log in to reply
 

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