The correct DP solution


  • 28
    N

    Here is the DP formula that leads to the right answer:

    • M(k) = money at the kth house
    • P(0) = 0
    • P(1) = M(1)
    • P(k) = max(P(k−2) + M(k), P(k−1))

  • -4
    class Solution(object):
        def rob(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            n = len(nums)
            if(n == 0):
                return 0
            if(n == 1):
                return nums[0]
            money = [0] * n
            money[0] = nums[0]     
               
            m1 = max(money[0], nums[1])
            money[1] = m1
            
            if(n <= 2):
                return money[n - 1]
            for i in range(2, n):
                m1 = money[i - 1]
                m2 = money[i - 2] + nums[i]
                money[i]= max(m1, m2)
            
            return money[n - 1]

  • 0
    J

    This is good, but since you don't need to reconstruct the actual solution, you could reduce it to O(1) space.


  • 0
    E

    Thanks for the recursion, really simplified what I was coming up with.


  • 0
    Y

    Seems over time limit.

    /* M(k) = money at the kth house */
    /* P(0) = 0 */
    /* P(1) = M(1) */
    /* P(k) = max(P(k−2) + M(k), P(k−1)) */
    class Solution {
        public:
            unordered_map<int, int> cache;
            int dp(vector<int>& nums, int i) {
                if(i < 0)
                    return 0;
                else if(i == 0)
                    return nums[0];
                else if(cache[i])
                    return cache[i];
                else {
                    int tmp = max(dp(nums, i-2)+nums[i], dp(nums, i-1));
                    cache[i] = tmp;
                    return tmp;
                }
            }
            int rob(vector<int>& nums) {
                return dp(nums, nums.size()-1);
            }
    };
    

  • 0
    C
    class Solution {
    public:
        int rob(vector<int>& nums) {
            if (nums.size() == 0)
                return 0;
                
            int len = nums.size();
            vector<int> res;
            res.push_back(0);
            res.push_back(nums[0]);
           
            int maxPro = max(res[0], res[1]);
    
            for (int i = 1; i < len; i++) {
                int present = max(res[i-1] + nums[i], res[i]);;
                res.push_back(present);
               
                if (present > maxPro)
                    maxPro = present;
           }
           
            return maxPro;
        }
    };
    

Log in to reply
 

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