lic int rob(int[] nums) {
int[] memo = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
memo[i] = -1;
}
return searchBottom2Top(0, nums, memo);
}
private int searchBottom2Top(int i, int[] nums, int[] memo) {
if (i >= nums.length) {
return 0;
}
if (memo[i] != -1) { // 其实这个地方不可能是-1,因为我们是递推
return memo[i];
}
return memo[i] = Math.max(searchBottom2Top(i + 1, nums, memo), nums[i] + searchBottom2Top(i + 2, nums, memo));
}
}
python版
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return self.searchBottom2Top(0, nums, [-1 for i in range(len(nums))])
def searchBottom2Top(self, i, nums, memo):
if i >= len(nums):
return 0
if memo[i] != -1: # 其实这个地方不可能是-1,因为我们是递推
return memo[i]
memo[i] = max(self.searchBottom2Top(i + 1, nums, memo), nums[i] + self.searchBottom2Top(i + 2, nums, memo))
return memo[i]
我想你在想,这和你之前见到的动态规划的写法还是不一致!
java版
class Solution {
public int rob(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
if (nums.length == 1) {
return dp[0];
}
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}
python版
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
dp = [0 for i in range(len(nums))]
dp[0] = nums[0]
if len(nums) == 1:
return dp[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
return dp[-1]
现在是不是很眼熟了,这就是动态规划,其实前面的也是,只是方式不同罢了!看到这里是不是思路很清晰了,动态规划并不难,难的是我们分析问题的出发点。看这道题目,我们从递归一步一步到动态规划!
其实递归的本质就是n -> n – 1 -> n
到这里,我们真正知道了什么是动态规划,还有两个概念,我想你应该知道
最优子结构
重叠子问题
结尾
一道题看清动态规划的前世今生,打算用三篇文章来通俗的解释dp的概念以及思考方式!如果你喜欢这篇文章,欢迎关注我GitHub。