Problem:
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Idea:
DP
Time complexity: O(n)
Space complexity: O(n) -> O(1)
Solution:
C++ / Recursion + Memorization
Time complexity: O(n)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Runtime: 0 ms class Solution { public: int rob(vector<int>& nums) { const int n = nums.size(); m_ = vector<int>(n, -1); return rob(nums, n - 1); } private: int rob(const vector<int>& nums, int i) { if (i < 0) return 0; if (m_[i] >= 0) return m_[i]; return m_[i] = max(rob(nums, i - 2) + nums[i], rob(nums, i - 1)); } vector<int> m_; }; |
C++ / DP
Time complexity: O(n)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua // Runtime: 3 ms class Solution { public: int rob(vector<int>& nums) { if (nums.empty()) return 0; vector<int> dp(nums.size(), 0); for (int i = 0; i < nums.size() ; ++i) dp[i] = max((i > 1 ? dp[i - 2] : 0) + nums[i], (i > 0 ? dp[i - 1] : 0)); return dp.back(); } }; |
C++ / O(1) Space
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Runtime: 3 ms class Solution { public: int rob(vector<int>& nums) { if (nums.empty()) return 0; int dp2 = 0; int dp1 = 0; for (int i = 0; i < nums.size() ; ++i) { int dp = max(dp2 + nums[i], dp1); dp2 = dp1; dp1 = dp; } return dp1; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment