媒介

本篇文章旨在用通俗简朴的语言来教你入门动态筹划。动态筹划是算法中很重要的一块内容，在各大公司的笔试算法中占据大壁山河，所以，把握动态筹划是你拿到称心的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]