设为首页 加入收藏

TOP

一道题看清动态规划的前世今生 ( 一 )(一)
2017-11-13 14:55:23 】 浏览:40
Tags:一道 看清 动态 规划 今生

前言

本篇文章旨在用通俗简单的语言来教你入门动态规划。动态规划是算法中很重要的一块内容,在各大公司的笔试算法中占据大壁江山,所以,掌握动态规划是你拿到称心的offer的前提,废话不多说,让我们来开始一段算法之旅吧。在开始之前,你要努力忘掉你理解的动态规划,因为有可能那些都是错误的,会限制你的思路。相信我,读完这篇文章你肯定会有收获。

前导技能

  • 递归 (熟悉递归运行原理)
  • 暴力搜索
  • 在线的智商

问题引入

在开始后续的工作之前,我们先来看一道非常简单的题目

题目

题目来源Leetcode

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.

题意很简单,我也就不翻译了。

跟着下面的步骤,仔细思考,在这之前,忘掉你对动态规划的理解!

暴搜,动态规划的前生

我假设你具备了我说的那些前导技能,相信你是一个暴搜出奇迹的天才。
那么,我们现在用暴力搜索来分析一下这道题目

现在,我们从最后一个商家开始,搜索我们想要的答案

那么我们现在应该有这样一个函数,假设它具备暴力搜索的功能。那么,我们首先返回已经”完成”的暴力搜索到的答案

java版

private int search(int i, int[] nums) {
	...
}
public int rob(int[] nums) {
	return search(nums.length - 1, nums);        
}

python版

def search(self, i, nums):
	pass
def rob(self, nums):
   return self.search(len(nums) - 1, nums)

现在,我们”基本”上已经完成了这道题目,因为暴搜对你来说很简单。其实上面这些文字,我只是在教你如何思考题目。接下来,让我们来完成暴搜的主体部分吧!

依据题意,我们不能盗窃相邻的商家,那么问题很简单了。搜索的状态只有两种,我们盗窃当前商家,然后跳过前面一个,继续判断前面的前面那家商家,或者我们不盗窃当前商家,往前走,因为前面有好家伙!这样,我们应该很容易完成search里面的内容

java版

private int search(int i, int[] nums) {
	if (i < 0) { // 没有商家了,我们要开始销赃
		return 0;
	}
	return Math.max(search(i - 1, nums), nums[i] + search(i - 2, nums));
}

python版

def search(self, i, nums):
	if i < 0: # 没有商家了,我们要开始销赃
		return 0
	return max(self.search(i - 1, nums), nums[i] + self.search(i - 2, nums))

记忆化搜索, 动态规划的今生

现在,我们已经得到了”正确”的答案。我们先来分析一下暴力搜索的时间复杂度吧

显然,这道题目,我们每个商家两个状态我们都模拟过了,那么很简单,时间复杂度就是O(2^n)
天啦噜,指数级的时间复杂度,你说你能走多远!

随便提一句,暴力搜索这类时间复杂度都和状态有关!

既然,这种暴搜我们”走不远”,那么怎么我们可以走得”更远呢”?

在此之前,我们先来直观得模拟一下我们暴搜的过程吧

# 现在我们用s(i)来表示我们上面的search方法
f(5) = max(f(4), nums[5] + f(3))
f(4) = max(f(3), nums[4] + f(2))
f(3) = max(f(2), nums[3] + f(1))
f(2) = max(f(1), nums[2] + f(0))
f(1) = max(f(0), nums[1] + f(-1) <=> nums[1]))

上面这个过程你看到了什么?
相信你肯定看出了我们重复计算了很多f()函数,因为你的智商在线!

是的,我们重复计算了前面我们计算过的数据,下面,我们根据这一点来优化一下刚才的暴力搜索

java版

class Solution {
    public int rob(int[] nums) {
        int[] memo = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            memo[i] = -1;
        }
        return search(nums.length - 1, nums, memo);
    }
    private int search(int i, int[] nums, int[] memo) {
	    if (i < 0) {
		    return 0;
	    }
        if (memo[i] != -1) {
            return memo[i];
        }
	    return memo[i] = Math.max(search(i - 1, nums, memo), nums[i] + search(i - 2, nums, memo));
    }
}

python版

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return self.search(len(nums) - 1, nums, [-1 for i in range(len(nums))])
    def search(self, i, nums, memo):
        if i < 0:
            return 0
        if memo[i] != -1:
            return memo[i]
        memo[i] = max(self.search(i - 1, nums, memo), nums[i] + self.search(i - 2, nums, memo))
        return memo[i]

上面,我们用一个memo数组来把我们计算过的数据保存一下,然后下一次用到时候直接返回即可!
这种方式的搜索,我们就叫它记忆化搜索!是不是很形象,记忆!

那么现在时间复杂度是多少呢?很明显是O(N)

现在我可以告诉你了,现在这种解法其实就是动态规划!你也许会说什么?你不是在逗我?但是我真的不是在逗你!
记忆化搜索就是递归版的动态规划,既然有递归版的,那么就有递推版的,我们仿照这个递归版的来写一下递推版的记忆化搜索!

java版

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

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目