设为首页 加入收藏

TOP

一道题看清动态规划的前世今生 ( 一 )(二)
2017-11-13 14:55:23 】 浏览:482
Tags:一道 看清 动态 规划 今生
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

首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇详解 Tomcat 的连接数与线程池 下一篇使用 FutureTask 的正确姿势

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目