C++ solution, using DP, O(n) time comlexity


  • 1
    A
    class Solution {
    public:
      int rob(vector<int>& nums) {
      	int n = nums.size();
      	if (n == 0)
      		return 0;
      	std::vector<int> dp(n,0);
      	dp[0] = nums[0];
      	dp[1] = std::max(nums[0],nums[1]);
      	for (int i = 2; i < n; i++) {
      		dp[i] = std::max(nums[i]+dp[i-2], dp[i-1]);
      	}
      	return dp.back();     
      }
    };

  • 0
    L

    what if nums.size() returns 1?
    dp[1] = std::max(nums[0],nums[1]);
    nums[1] will visit invalid memory


Log in to reply
 

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