万字长文 | 面试高频算法题之动态规划系列
大家好，我是程序员学长~
如果喜欢，记得点个关注哟~
动态规划
全文概览
动态规划基础知识
问题模型
最优子结构
最优子结构规定了原问题和子问题的关系。原问题的最优解包含子问题的最优解。反过来说，我们可以通过子问题的最优解来求出原问题的最优解。 无后效性
（1）无后效性是指在推导后面阶段状态的时候，只依赖于前面阶段的的状态，而不会去关心这个状态是怎么一步步得来的。比如斐波那契数列 F(5)=F(4)+F(3)，则可以看出 F(5) 只依赖于 F(4) 和 F(3) 这两个状态的值，而不用管他们是如何得来的。 （2）一旦某个状态确定了，就不受之后阶段的决策影响。
重复子问题
就是原问题经过拆分成多个子问题时，子问题和子问题之间存在重复计算的情况。
下面我们结合实例，来比较透彻的理解一下上面的理论部分。
问题描述：
min(i,j) = w[i][j] + min(min(i-1,j), min(i,j-1))
求解思路
解决动态规划问题，一般有状态转移表法和状态转移方程法这两种方法。
状态转移表法
接下来我们来看一下如何用状态转移表法来求最短路径这个问题的。
代码实现如下所示：
def minDis(data,n):
status=[[0 for _ in range(n)] for _ in range(n)]
sum=0
#第一行赋值
for i in range(n):
sum=sum+data[0][i]
status[0][i]=sum
#第一列赋值
sum=0
for i in range(n):
sum=sum+data[i][0]
status[i][0]=sum
for i in range(1,n):
for j in range(1,n):
status[i][j]=data[i][j]+min(status[i-1][j],status[i][j-1])
return status[n-1][n-1]
data=[[1,3,5,7,2],
[3,6,5,2,1],
[7,4,1,6,5],
[1,3,8,2,3],
[4,3,1,6,4]]
n=5
print(minDis(data,n))
状态转移方程法
对于最短路径这个例子，它的状态转移方程如下所示：
min(i,j) = w[i][j] + min(min(i-1,j), min(i,j-1))
import sys
data=[[1,3,5,7,2],
[3,6,5,2,1],
[7,4,1,6,5],
[1,3,8,2,3],
[4,3,1,6,4]]
n=5
mem=[[0 for _ in range(5)] for _ in range(5)]
def minDis(i,j):
if i==0 and j==0:
return data[0][0]
if mem[i][j]>0:
return mem[i][j]
minLeft = sys.maxsize
if j-1>=0:
minLeft=minDis(i,j-1)
minUp = sys.maxsize
if i-1>=0:
minUp=minDis(i-1,j)
current=data[i][j]+min(minLeft,minUp)
mem[i][j]=current
return current
print(minDis(n-1,n-1))
斐波那契数
509. 斐波那契数
问题描述
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。
示例：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
分析问题
我们把整个求解过程分为 n 个阶段，每个阶段去求解数列对应项的值。我们在解决当前问题时，也就是求解该对应项的值的时候，会依赖过去的状态，也就是前面几项的值来计算。比如我们在求解 F(6) 的时候，我们需要用到 F(5) 和 F(4) 这两项。
我们来定义一个数组，来记录每项的状态。这个数组也叫做状态转移矩阵。按照斐波那契数列的定义：
F(0)=0, F(1)=1
F(n)=F(n-1)+F(n-2) (n>=2)
从中可以知道 F(n) 的值只与它的前两个状态有关。所以我们只要知道它的前两个状态，就可以求出 F(n)。
初始化值 F(0)=0，F(1)=1，我们直接放入数组中。 要想计算F(2)，我们需要知道 F(0) 和 F(1)，因为上一步已经放入数组中，我们直接拿来用就好了，然后把 F(2) 的结果放入数组中。 要想计算F(3)，我们需要知道 F(2) 和 F(1)，因为 F(2) 和 F(1) 已经存在数组里了，我们直接拿来用就好了，然后把 F(3) 的结果放入数组中。 ....
依此类推，直到计算到 n 为止。整个状态转移矩阵就计算好了。如下图所示。我们以求解 F(5) 为例。
代码如下所示：
def fibs(n):
if n<2:
return n
dp=[0 for _ in range(n+1)]
dp[0]=0
dp[1]=1
for i in range(2,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]
print(fibs(6))
跳台阶问题
70. 爬楼梯
问题描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
示例：
输入：2
返回值：2
说明：青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2。
分析问题
拿到这个问题，我们可以反过来思考，要想爬到n级台阶，我们只能从n-1级跳1级或者从n-2级跳2级两种可能。我们用f(x)来表示爬到x级台阶的方案数，那么可以得出f(x)=f(x-1)+f(x-2)。有了递推公式，我们就可以采用动态规划的方法来解决问题了。
class Solution():
def climbStairs(self,n):
if n==0 or n==1:
return 1
dp=[]
dp[0]=1
dp[1]=1
for i in range(2,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]
我们可以看到该算法的时间复杂度是O(n)，空间复杂度也是O(n)。由于爬到n级台阶的跳法只是依赖于n-1级和n-2级的跳法，所以我们不需要保存之前每一级台阶的跳法数。最需要保存它前两个台阶的跳法数就好。
class Solution():
def climbStairs(self,n):
if n==0 or n==1:
return 1
p=0
q=0
r=1
for i in range(1,n+1):
p=q
q=r
r = p + q
return r
我们可以看到该算法的时间复杂度是O(n)，空间复杂度是O(1)。
连续子数组的最大和
LeetCode 53. 最大子数组和
问题描述
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
示例：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6
分析问题
因为题目是求所有子数组的和的最大值，我们可以假设以第i个数结尾的连续子数组和的最大的值为f(i)。现在我们只需要求出所有的f(i)，拿出其中最大的就是题目的解。
我们下面来看一下如何求解f(i)。对于以第i个数结尾的子数组来说，f(i)要么等于nums[i]，要么等于f(i-1)+nums[i]，这取决于nums[i]和f(i-1)+nums[i]的大小。即f(i)=max(nums[i],f(i-1)+nums[i])。
class Solution:
def FindGreatestSumOfSubArray(self, array):
if array is None or len(array)==0:
return 0
n=len(array)
dp=[0]*n
dp[0]=array[0]
for i in range(1,n):
dp[i]=max(array[i],dp[i-1]+array[i])
return max(dp)
我们可以看到这里的时间复杂度和空间复杂度都是O(n)。由于我们在求解f(i)的时候，只和f(i-1)和nums[i]有关，而和f(i-2)、f(i-3)...无关，所以，我们只需要一个变量去保存f(i-1)就好了，这样可以把空间复杂度减低为O(1)。下面我们来看一下代码如何实现。
def maxSubArray(array):
if array is None or len(array)==0:
return 0
n=len(array)
pre=array[0]
result=array[0]
for i in range(1,n):
pre=max(array[i],pre+array[i])
result=max(result,pre)
return result
买卖股票的最好时机I
LeetCode 121. 买卖股票的最佳时机
问题描述：
给定一个数组prices，它的第i个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。
示例：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
分析问题：
拿到这个问题，我们就需要先思考用什么样的思想去解决。我们来看这个题目，这个问题是求最优解问题。初看题目，我们最容易想到的方法，就是暴力求解，即遍历数组，求出最大值和最小值，相减就是最大利润。不过这里有一个隐含条件，就是股票的卖出时机必须大于股票的买入时机。
def maxProfit(prices):
#最大利润
ans = 0
#股票卖出时机要大于股票买入时机
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
ans = max(ans, prices[j] - prices[i])
return ans
prices=[7, 1, 5, 3, 6, 4]
maxProfit(prices)
我们可以看出，这种求解的方法，时间复杂度是O(n^2)，那有没有时间复杂度更优的方法呢？
首先，我们来分析一下这个问题符合什么“问题模型”呢？我们从0开始走，走到n-1，一共需要走n-1步，也就对应着n-1个阶段。每个阶段都只能往右走，并且每个阶段都会对应一个状态集合，我们把状态定义为maxprofit[i]，其中i表示走到哪一步，maxprofit[i]的值表示从开始走到位置i的最大利润是多少。所以这个问题是“多阶段决策最优”问题，对于这类问题，我们首先要考虑能否用动态规划的思想来解决，也就是看是否符合动态规划的特征：重复子问题、无后效性、最优子结构。
无后效性：我们要想计算maxprofit[i]这个状态，只需要关心maxprofit[i-1]的状态，并不关心maxprofit[i-1]这个状态是如何生成的。而且，我们只能往后移动，不允许后退。所以，前面阶段的状态确定之后，不会被后面阶段的决策所改变。所以符合"无后效性"。
重复子问题：如果要达到maxprofit[i]这个状态，我们可以有不同的决策序列。比如假设第五天，我们的最大利润是8，即maxprofit[i]的状态为8，我们可以是第一天买入2，第三天卖出10。也可以第二天买入2，第三天卖出10。
最优子结构：因为maxprofit[i]可以通过maxprofit[i-1]推导出来，即符合“最优子结构”
maxprofit[i]=max(maxprofit[i-1],prices[i]-minprice)
下面我们看代码如何实现：
def maxProfit(prices):
n=len(prices)
if n==0:
return 0
maxPRofit=[0]*n
minprice=prices[0]
for i in range(1,n):
minprice = min(minprice, prices[i])
maxPRofit[i]=max(maxPRofit[i-1],prices[i]-minprice)
return maxPRofit[-1]
prices=[7, 1, 5, 3, 6, 4]
print(maxProfit(prices))
我们可以看出，这种求解的时间复杂度为O(n)。
买卖股票的最佳时机 II
LeetCode 122. 买卖股票的最佳时机 II
问题描述
给定一个数组 prices，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
分析问题
这个问题的解题思路和上题类似，也是“多阶段决策最优”问题。也符合动态规划解题模型。不过这里的“状态”会有所区别，我们来看一下。考虑到 “不能同时参与多笔交易”。所以，每天交易结束后手里只可能存在有股票和没有股票两种状态。所以，我们可以用二个数组来表示，其中dp1[i]表示第i天交易后，手里没有股票的最大利润。dp2[i]表示第i天交易完成后，手里有股票的最大利润。
dp1[i]表示第i天手里没有股票的最大利润，那么这个状态要么是由dp1[i-1]，即前一天手里没有股票的最大利润，转移过来。要么由dp2[i-1]+prices[i]，即前一天手里有股票，今天把这个股票卖出。所以dp1[i]的状态转移方程为：
dp1[i]=max(dp1[i-1],dp2[i-1]+prices[i])
dp2[i]表示第i天手里有股票的最大利润，那么这个状态要么是由dp2[i-1]，即前一天手里有股票的最大利润，转移过来。要么由dp1[i-1]-prices[i]，即前一天手里没有股票，今天把这个股票进行买入。所以dp2[i]的状态转移方程为：
dp2[i]=max(dp2[i-1],dp1[i-1]-prices[i])
所以我们代码实现如下所示：
def maxProfit(prices):
n=len(prices)
if n==0:
return 0
dp1=[0]*n
dp2=[0]*n
#手里没有股票
dp1[0]=0
#手里有股票
dp2[0]=-prices[0]
for i in range(1,n):
dp1[i]=max(dp1[i-1],dp2[i-1]+prices[i])
dp2[i]=max(dp2[i-1],dp1[i-1]-prices[i])
return dp1[n-1]
prices=[7, 1, 5, 3, 6, 4]
print(maxProfit(prices))
买卖股票的最佳时机 III
123. 买卖股票的最佳时机 III
问题描述
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
分析问题
这个题目和上个题相比，状态又发生了变化，这里因为限制了交易次数，所以我们需要把交易次数的状态也保存起来。所以每天交易结束后，有5种状态。
未进行过任何操作。
只进行过一次买入操作。
进行过一次买入和卖出操作。
完成一笔的交易前提下，进行了第二次买入操作。
完成两笔交易。
由于第一个状态的利润为0，所以我们不需要记录。我们把剩下的4个状态分别用buy1，sell1，buy2，sell2来表示。下面我们来看一下如何根据前一天的状态，来通过转移方程生成今天的4个状态。
对于buy1而言，我们可以今天不操作，直接通过昨天的buy′ 1转移过来，或者我们从未进行过任何操作前提下，今天买入股票。
buy1 =max(buy′ 1,-prices[i])
对于sell1而言，我们今天可以不做任何操作，直接通过昨天的sell′ 1转移过来，或者我们可以在只进行过一次买入交易的前提下，今天把股票卖出。
sell1=max(sell′ 1,buy′ 1+prices[i]）
对于buy2而言，我们今天可以不做任何操作，直接通过昨天的buy′ 2转移过来，或者，我们在进行过一笔完成的交易条件下，今天再把该股票买入。
buy2=max(buy′ 2,sell′ 1-prices[i]）
对于sell2而言，我们今天可以不做任何操作，直接通过昨天的sell′ 2 转移过来，或者，我们在buy2的前提下，今天把股票卖出。
sell2=max(sell′ 2,buy′ 2+prices[i]）
Tips：我们在计算sell1时，我们可以直接使用buy1而不是buy′ 1进行转移。buy1比buy′ 1多考虑的是在第i天买入股票的情况，而转移到sell1时，考虑的是在第i天卖出股票的情况，这样在同一天买入并且卖出股票的收益为0，不会对结果产生影响。对于buy2和sell2也是同样的考虑，我们可以直接用第i天求出的值来进行转移。
我们来看代码实现：
def maxProfit(prices):
n = len(prices)
#表示以prices[0]买入股票
buy1=-prices[0]
#表示在同一天买入并且卖出，即为0
sell1=0
#表示同一天买入卖出后再以prices[0]的价格买入
buy2=-prices[0]
#表示同一天买入卖出两次，即为0
sell2 = 0
for i in range(1, n):
buy1 = max(buy1, -prices[i])
sell1 = max(sell1, buy1 + prices[i])
buy2 = max(buy2, sell1 - prices[i])
sell2 = max(sell2, buy2 + prices[i])
return sell2
prices=[7, 1, 5, 3, 6, 4]
print(maxProfit(prices))
接雨水问题
42. 接雨水
问题描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例：
输入：height = [4,2,0,3,2,5]
输出：9
解释：上面是由数组 [4,2,0,3,2,5] 表示的高度图，在这种情况下，可以接 9 个单位的雨水（蓝色部分表示雨水）。
分析问题
我们最直观的想法就是，对于数组中的每个元素，下雨后能存水的高度等于它两边最大高度的较小值减去当前高度的值。比如对于数组中第二个元素，它能储水的高度就是min(maxleft,maxright)-height[1]=4-2=2。
对于求它两边的最大高度，我们可以以当前元素为基准，分别进行向左和向右扫描来求得。
下面我们来看一下代码实现。
def result(height):
ans=0
n=len(height)
for i in range(1,n):
maxleft=0
maxright=0
##向左扫描
for j in range(i, -1, -1):
maxleft=max(maxleft,height[j])
##向右扫描
for j in range(i,n):
maxright=max(maxright,height[j])
ans=ans+min(maxleft,maxright)-height[i]
return ans
height=[4,2,0,3,2,5]
print(result(height))
我们可以很明显的看到，对于数组中的每一个元素，我们都需要向左和向右进行扫描，所以这个算法的时间复杂度为O(n^2)。
优化
我们可以发现在上个算法中，我们对于数组中的每个元素都需要花费O(n)的时间去向左和向右扫描，去寻找两边的最大值。如果我们可以提前知道每个位置对应的两边的最大高度，则可以在O(n)的时间内去求得雨水的总量。
下面我们来看一下如何通过预处理来得到每个元素对应的两边的最大高度。
我们先来看一下如何求每个位置对应的左边的最大高度，对于元素height[i]来说，leftmax要么是它本身，要么是heght[i-1]对应的leftmax的值，即leftmax[i]=max(leftmax[i-1]，height[i])，其中**leftmax[i]**表示下标i及其左边的位置中，height的最大高度。
同理可以求得，rightmax[i]=max(rightmax[i+1]，height[i])，其中**rightmax[i]**表示下标i及其右边的位置中，height的最大高度。
下面我们来看一下代码如何实现。
def result(height):
if not height:
return
n=len(height)
##求出左边最大
leftmax=[0]*n
leftmax[0]=height[0]
for i in range(1,n):
leftmax[i]=max(leftmax[i-1],height[i])
rightmax=[0]*n
rightmax[n-1]=height[n-1]
for i in range(n-2,-1,-1):
rightmax[i]=max(rightmax[i+1],height[i])
ans = 0
for i in range(0,n):
ans=ans+min(leftmax[i],rightmax[i])-height[i]
return ans
height=[4,2,0,3,2,5]
print(result(height))
通过代码，我们可以清楚的知道，这个算法的时间复杂度为O(n)，空间复杂度也为O(n)。
终极解法
在优化算法中，我们引入了两个数组leftMax和rightMax来保存每个位置对应的两边的最大高度，因此空间复杂度为O(n)，那我们有什么方法可以来降低空间复杂度吗？
我们可以观察到，对于下标i处能接的雨水量是由leftMax[i]和rightMax[i]中的最小值决定。由于数组leftMax是从左往右计算，而数组rightMax是从右往左计算，所以我们可以使用双指针和两个变量来替代这两个数组，下面我们来看一下。
我们维护两个指针left和right，以及两个变量leftMax和rightMax，初始时left=0，right=n-1，leftMax=0，rightMax=0。指针left只能往右移动，指针right只能往左移动，然后在移动的过程中，去更新变量leftMax和rightMax的值。
在开始阶段left=0，right=n-1，leftMax=0，rightMax=0。然后**height[left]和height[right]**进行比较。这时会出现两种情况：
1.如果此时height[left]<height[right]，则leftMax=max(leftMax,height[left])=height[left]<height[right]=rightMax，所以下标left处能接的雨水量为leftMax-height[left]，然后left往右移动一位，此时left=left+1=1。
2.如果此时height[left]>=height[right]，则leftMax=max(leftMax,height[left])=height[left]>=height[right]=rightMax，所以下标right处能接的雨水量位rightMax-height[right]，然后right往左移动一位，此时right=right-1=n-2。
然后循环执行1，2步，直到left和right相遇为止。
下面我们来总结一下，在指针left和right没有相遇时，我们执行如下操作。
1.使用height[left]和height[right]来更新leftMax和rightMax。
2.如果height[left]<height[right]，则必有leftMax<rightMax。下标left处能接的雨水量为leftMax-height[left]，然后left往右移动一位。
3.如果height[left]>=height[right]，则必有leftMax>=rightMax。下标right处能接的雨水量为rightMax-height[right]，然后right往左移动一位。
下面我们来看一下代码的实现。
def result(height):
if not height:
return
n=len(height)
left=0
leftMax=0
right=n-1
rightMax=0
ans = 0
while left < right:
leftMax=max(leftMax,height[left])
rightMax=max(rightMax,height[right])
if height[left] < height[right]:
ans=ans+leftMax-height[left]
left=left+1
else:
ans=ans+rightMax-height[right]
right=right-1
return ans
height=[4,2,0,3,2,5]
print(result(height))
我们通过分析代码可以很容易的知道，这个算法的时间复杂度是O(n)，空间复杂度为O(1)。
求路径
62. 不同路径
问题描述
一个机器人在 m×n 大小的地图的左上角（起点）。机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？
示例：
输入：m = 3，n = 2 输出：3 解释：从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向下 -> 向下 向下 -> 向下 -> 向右 向下 -> 向右 -> 向下
分析问题
根据题意，由于机器人只能选择往下走或者往右走，所以对于右下角位置matrix[m-1] [n-1]来说，它可以由该位置的上面向下走，即从matix[m-2] [n-1] 向下走 ，也可以由该位置的左边向右走，即从matrix[m-1] [n-2] 向右走。
我们定义一个m*n的矩阵dp，其中dp[i] [j]表示从起点到达第i行第j列的方案数。根据前面的分析，我们可以清楚的知道，dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。所以，我们可以采用动态规划思想来求解，其状态转移方程为 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。
对于第一行的元素来说，我们只有一种走法，即只能从左边位置向右走；对于第一列元素来说，也只有一种走法，只能从上边位置向下走。
下面我们来看一下代码如何实现。
class Solution:
def uniquePaths(self,m ,n):
#申请一个m行n列的矩阵，赋值为1
dp = [[1 for _ in range(n)] for _ in range(m)]
#填充矩阵dp
for i in range(1,m):
for j in range(1,n):
#根据状态转移方程，填充矩阵
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
该算法的时间复杂度和空间复杂度都是O(m*n)。
优化
我们知道，从左上角移动到右下角，一共需要走m-1+n-1步，其中包含m-1步向下，n-1步向右。由于只能向下或者向右走，所以当我们从这m+n-2步中选择m-1次向下走，则剩下的n-1步只能向右走（或者选其中的n-1步向右走，剩下的m-1步只能向下走），所有总的方案数为 C(m+n-2, m-1)或者C(m+n-2, n-1)，没错，这就是数学上的排列组合问题。
**Tips: C(n,m)=n * (n-1) ... (n-m+1) / (m * (m-1) * (m-2) ... * 1) **
class Solution:
def uniquePaths(self,m ,n):
#一共n+m-2步
#C(n,m)= n * (n-1) *...* (n-m+1) / (m * (m-1) * (m-2) ... * 1)
count = n + m - 2
#选择n-1步向右走
k = n - 1
num = 1.0
for i in range(1,k+1):
num=num * (count - k + i ) / i
return int(num)
矩阵的最小路径和
64. 最小路径和
问题描述
给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
示例：
输入：[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
输出：12
分析问题
因为题目要求每次只能向右或者向下走，所以对于右下角的位置，只能通过两种方式到达，即
右下角的上方位置向下走。 右下角的左边位置向右走。
所以，对于最后一个状态来说，它只依赖于它上边的状态和它左边的状态，而与其它状态无关。因此，我们可以使用动态规划来求解，
其状态转移方程是 **dp[i] [j] = min(dp[i-1] [j] ，dp[i] [j-1])+matrix[i] [j] **。
下面我们来看一下临界条件，对于第一行的元素来说，它不能从它上边的状态转移过来，只能从左边的状态转移过来，所以第一行的状态转移方程为 dp[0] [j] = d[0] [j-1] + matrix[0] [j]。同理可知，对于第一列的元素来说，它不能从它左边的状态转移过来，只能从它的上边转移过来，所以第一列元素的状态转移方程为 dp[i] [0] = dp[i-1] [0] + matrix[i] [0]。
class Solution:
def minPathSum(self , matrix ):
# write code here
m=len(matrix)
if m==0:
return 0
n=len(matrix[0])
#定义状态转移矩阵
dp=[[0]*n for _ in range(m)]
#第一个元素是matrix[0][0]
dp[0][0]=matrix[0][0]
#处理第一列元素
for i in range(1,m):
dp[i][0]=dp[i-1][0] + matrix[i][0]
#处理第一行元素
for j in range(1,n):
dp[0][j]=dp[0][j-1] + matrix[0][j]
for i in range(1,m):
for j in range(1,n):
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j]
#最后一个元素就是最小路径和
return dp[m-1][n-1]
该算法的时间复杂度和空间复杂度都是O(m*n)，其中m代表矩阵的行数，n代表矩阵的列数。
其实，我们也不需要重新申请一个空间dp，我们可以直接复用matrix即可。
class Solution:
def minPathSum(self , matrix ):
# write code here
m=len(matrix)
if m==0:
return 0
n=len(matrix[0])
#处理第一列元素
for i in range(1,m):
matrix[i][0]=matrix[i-1][0] + matrix[i][0]
#处理第一行元素
for j in range(1,n):
matrix[0][j]=matrix[0][j-1] + matrix[0][j]
for i in range(1,m):
for j in range(1,n):
matrix[i][j]=min(matrix[i-1][j],matrix[i][j-1])+matrix[i][j]
#最后一个元素就是最小路径和
return matrix[m-1][n-1]
丢棋子问题
问题描述
一座大楼有 n+1 层，地面算作第0层，最高的一层为第 n 层。已知棋子从第0层掉落肯定不会摔碎，从第 i 层掉落可能会摔碎，也可能不会摔碎。给定整数 n 作为楼层数，再给定整数 k 作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。一次只能扔一个棋子。
示例
输入：10,1
输出：10
说明：因为只有1棵棋子，所以不得不从第1层开始一直试到第10层，在最差的情况下，即第10层是不会摔坏的最高层，最少也要扔10次
分析问题
首先，我们令 f(n,k) 表示n层楼，k个棋子，在最差的情况下扔的最小实验次数。
我们来考虑一枚棋子从第j层扔下去，它会发生两种状态，即碎了和没碎。
碎了，说明从第j层以上的层数扔下去必然还是碎的，所以可以忽略大于j的层数，此时只剩下了k-1枚棋子和j-1层楼，剩下的实验次数为f(j-1,k-1)。 没碎，说明第j层和第j层以下的层数扔下必定还不碎，所以可以忽略小于j的层数，此时还有k枚棋子（因为这一枚棋子没碎，所以还能用）和 n-j 层楼，剩下的实验次数为 f(n-j，k)。
这里有一些特殊情况需要考虑一下。
若 n=0 , 此时在地面，肯定不会摔碎，所以不需要做任何实验，故f=0 若 k=1 ，表示只有一个棋子，我们必须逐层去操作，最坏的情况，即第n层楼才会摔碎，此时需要n次实验，故f=n。
因为我们不知道从第j层扔下棋子会不会摔碎，而题目要求的是求最差的情况，即以上两种情况的最大值，并且j的取值是不确定的，它的取值范围为是[1, n]，因此，我们需要枚举所有的j，计算j的所有取值中对应次数最小的那一个，才能表示最少的实验次数。
我们可以使用递归来求解，下面我们来看一下代码实现过程。
import sys
class Solution(object):
def solve(self,n,k):
#特殊条件
if n==0:
return 0
if k==1:
return n
res=sys.maxsize
#j的范围是[1,n]
for j in range(1,n+1):
#求最差情况下的最小的实验次数
res = min(res, 1 + max(self.solve(j - 1, k - 1), self.solve(n - j, k)))
return res
该算法的时间复杂度是O(n！)，空间复杂度是O(1)。该算法的时间复杂度太高，我们来看一下如何进行优化。
优化
这道题我们可以使用动态规划来求解。根据上面推导出的关系式可以知道，动态规划的转移方程为:
dp[i] [j] = min (1 + max (dp[p-1] [j-1] , dp[i-p] [j] ) ) ，其中p的范围是[1,k]
dp[i][j] 表示i层楼，j个棋子, 在最差情况下的最少实验次数。
下面我们来看一下代码实现。
import sys
class Solution(object):
def solve(self,n,k):
if n==0:
return 0
if k==1:
return n
dp=[[0] * (k+1) for _ in range(n+1)]
print(dp)
#其中dp[i][1] = i，dp[0][k] = 0
for i in range(1,n):
dp[i][1]=i
for i in range(1, n+1):
for j in range(2,k+1):
dp[i][j]=sys.maxsize
for p in range(1,i+1):
#转移方程
dp[i][j] = min(dp[i][j],1+max(dp[p-1][j-1],dp[i-p][j]))
return dp[n][k]
该算法的时间复杂度是O(n^2 * k) ，空间复杂度是O(nk)。
终极解法
这里我们使用反向思维来求解，题目是求n层楼，k个棋子在最坏的情况下最少需要扔多少次。现在我们将问题逆向化，看i个棋子扔j次，最多可以测多少层楼这个问题（含义是指每次扔的位置都是最优的并且在棋子肯定够用的情况下），这里用dp[i] [j]来表示。
下面我们考虑第i个棋子在最优的楼层扔下去，有两种情况发生。
碎了，那么上面就不需要测了，下面能测 dp[i-1] [j-1] 层。 没碎，那么下面就不需要测了，上面能测 dp[i] [j-1] 层。 第i个棋子扔掉的那一层也能测。
综上所述，考虑最差的情形（即i个棋子扔 j 次，最多可测的的楼层数），可以求出状态转移方程为：
dp[i] [j] = dp[i-1] [j-1] + dp[i] [j-1] + 1
初始时：因为不管有多少个棋子，扔一次就只能测一层楼，所以dp[i] [1] =1。
最终答案：i 不超过k时候, 使得dp[i] [j] >= n的最小的j。
下面我们还可以有两个优化。
我们知道N层楼用二分的方式扔log2N+1次就能直接确定哪层楼是棋子不会摔碎的最高层数，所以当给定的棋子数大于logN+1时，我们就直接返回log2N+1。
由于状态转移方程为 dp[i] [j] = dp[i-1] [j-1] + dp[i] [j-1] + 1 ，即dp[i] [j] 只和它左上面的元素 dp[i-1] [j-1] 和 它左边的元素 dp[i] [j-1]，所以我们可以压缩为一维，并且需要从右往左计算，如下图所示：
如图所示，我们这里用粉色来表示dp[i] [j] ，用黄色来表示dp[i] [j-1] 。在计算dp[j] 的时候，我们从右往左遍历，一开始dp[j] 处为黄色，存储的是上一次迭代的结果dp[i] [j-1] , j-1处也为黄色，因此dp[j] = dp[j] + dp[j-1] + 1 就等价于 dp[i] [j] = dp[i] [j-1] + dp[i-1] [j-1] + 1。
下面我们来看一下代码的实现。
import sys
import math
class Solution(object):
def solve(self,n,k):
if n==0:
return 0
if k==1:
return n
#优化性质, 如果k充分大, 二分的扔即可
b = int(math.log2(n) + 1)
if k >= b:
return b
dp = [1] * (k+1)
res=1
while True:
res=res+1
for j in range(k,1,-1):
print(j)
dp[j] = dp[j] + dp[j-1] + 1
if dp[j] >=n:
return res
dp[1]=res
该算法的时间复杂度是O(klogN)，因为外层循环while最多迭代logn轮，否则可以直接使用二分扔棋子的方式来求解，内层循环是k次，所以总的时间复杂度是O(klogn)，空间复杂度是O(n)。
换钱的最少货币数
322. 零钱兑换
问题描述
给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。如果无解，请返回-1.
示例：
输入：coins = [1, 2, 5]，amount = 11
输出：3
说明：11 = 5 + 5 + 1
分析问题
由于题目是求最优解问题，所以我们最直观的感觉就是这题是否可以使用动态规划来求解。
我们都知道，对于求解动态规划相关的问题，最重要的就是求出状态转移方程。下面我们来看一下如何求解，首先我们定义F(S) 为组成金额 S 所需的最少货币数量。
假设目前我们已经知道了F(S)，和最后一枚货币的面值是C，我们就可以得出:
由于最后一枚货币的面值是未知的，所以我们需要枚举每个货币的面额值 C0， C1，.....，Cn-1，并选择其中的最小值。即
F(S)=min {F(S-C0) ，F(S-C1)，F(S-C3)，....，F(S-Cn-1)} + 1
其中： S-Ci >=0 当S=0时，F(S)=0 当n=0时，即货币的种类为0时，F(S)无解，即F(S)=-1
所以，F(S)的状态转移方程为：
F(S)=min {F(S-C0) ，F(S-C1)，F(S-C3)，....，F(S-Cn-1)} + 1
其中 Cj 代表的是第 j 枚货币的面值，即我们枚举最后一枚货币面额是Cj，那么F(S)需要从S-Cj这个金额对应的状态 F(S-Cj) 转移过来，再加上枚举的这枚货币数量1的贡献。由于题目是求货币的数量最少，所以 F(S)为前面能转移过来的状态的最小值。
假设 coins= [1, 2, 5]，amount = 11，即F(11) = min(F(10), F(9), F(6)) + 1。
下面我们来看一下代码的实现。
import sys
class Solution:
def coinChange(self, coins,amount):
dp = [sys.maxsize] * (amount + 1)
#S为0时，需要的货币数为0
#S<0时，直接忽略dp[S]
dp[0] = 0
for coin in coins:
#忽略S<0的。
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != sys.maxsize else -1
该算法的时间复杂度是O(Sn)，其中S是金额数，n是不同面额的个数。空间复杂度是O(S)。
最大正方形
221. 最大正方形
问题描述
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例：
输入：matrix = [["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]]
输出：4
分析问题
我们都知道正方形的面积等于边长的平方，要想求出最大的正方形面积，首先需要找到最大正方形的边长，然后在计算平方就好。
最直观的解法就是使用暴力法来求解。具体来说，我们遍历矩阵中的每一个元素，每次遇到1时，则将该元素作为正方形的左上角；然后根据左上角所在的行和列计算可能的最大正方形的边长（每次在下方新增一行以及在右方新增一列，判断新增的行和列是否满足所有元素都是 1）。
下面我们来看一下代码的实现。
class Solution:
def maximalSquare(self, matrix):
#如果矩阵为空，直接返回0
if len(matrix) == 0 \
or len(matrix[0]) == 0:
return 0
#最大的边长
max_length=0
rows, columns = len(matrix), len(matrix[0])
for i in range(rows):
for j in range(columns):
#遇到一个 1 作为正方形的左上角
if matrix[i][j] == '1':
max_length = max(max_length, 1)
#求出超出边界的最小值
current_edge = min(rows - i, columns - j)
for k in range(1, current_edge):
#判断新增的一行一列是否均为1
tag = True
#判断对角线是否为1，如果为0，直接退出，
if matrix[i + k][j + k] == '0':
break
for m in range(k):
#判断对应的列或者行是否全为1
if matrix[i + k][j + m] == '0' or matrix[i + m][j + k] == '0':
tag = False
break
if tag:
#如果新增的一行一列均为1，则增加边长
max_length = max(max_length, k + 1)
else:
break
#返回最大面积
result = max_length * max_length
return result
该算法的时间复杂度是 O(m * n * min(m, n) ^ 2)，其中 m 和 n 是矩阵的行数和列数；空间复杂度是O(1)。显然该算法的时间复杂度太高，下面我们来看一下如何进行优化求解。
这道题我们可以使用动态规划来求解。我们用 dp[i] [j] 表示以 (i，j) 为右下角，且只包含 1 的正方形的边长的最大值。在求出所有的dp[i] [j]的值以后，那么其中的最大值就是矩阵中只包含1的正方形的边长的最大值，其平方就是最大正方形的面积。下面我们来看一下如何来求解dp[i] [j] 。
对于矩阵中的每一个位置（i，j），检查其对应的值。
如果该位置是0，那么dp[i] [j] =0，因为当前位置不可能在由1组成的正方形中；
如果该位置是1，那么dp[i] [j] 的值由其上边，左边以及左上角三个相邻位置的值决定。即当前位置的值等于三个相邻位置元素对应的值的最小值加1。
dp[i] [j] = min( dp[i-1] [j] , dp[i] [j-1] , dp[i-1] [j-1] ) + 1
我们来看一下边界条件。当i=0或者j=0时，如果矩阵中位置为(i, j) 的值为1，那么以位置（i,j）为右下角的矩阵的边长只能是1，即此时dp[i] [j] = 1。
当matrix 为 [["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]] 时，其状态转移矩阵如下图所示。
下面我们来看一下代码的实现。
class Solution:
def maximalSquare(self, matrix):
#如果矩阵为空，直接返回0
if len(matrix) == 0 \
or len(matrix[0]) == 0:
return 0
max_edge = 0
m, n = len(matrix), len(matrix[0])
#初始化一个状态转移矩阵
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
#边界条件
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
max_edge = max(max_edge, dp[i][j])
#求出最大正方形
result = max_edge * max_edge
return result
该算法的时间复杂度是O(m*n)，其中m、n分别为矩阵的行和列。空间复杂度也是O(m * n)。
子数组的最大乘积
LeetCode 152. 乘积最大子数组
问题描述
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例：
输入：[2,3,-2,4]
输出：6
说明：子数组 [2,3] 有最大乘积 6。
分析问题
这道题和求子数组的最大和很像，建议大家先去看 53. 最大子序和。这里我们假设以第i个数结尾的连续子数组的最大乘积为fmax(i)，对于以第i个数结尾的子数组来说，因为nums[i]有可能是正数，也有可能是负数，需要分两种情况来讨论。
如果nums[i]为整数，那么fmax(i)要么等于nums[i]，要么等于fmax(i-1) * nums[i]，即fmax(i)=max(nums[i],fmax(i-1)+nums[i])。 如果nums[i]为负数，那么fmax(i)要么等于nums[i]，要么等于以它前一个位置结尾的最小值和nums[i]的乘积，因为一个负数乘以一个最小值，它的结果反而大。这里我们假设以第i个数结尾的连续子数组的最小乘积为fmin(i)，因此可以得出fmax(i)=max(nums[i], fmin(i-1) *nums[i])。
综上所述，对于以第i个数结尾的连续子数组来说，我们需要维护两个状态，即最大乘积fmax(i)和最小乘积fmin(i)，且状态转移方程为：
fmax(i) = max {fmax(i-1) * nums[i] , nums[i] , fmin(i-1) * nums[i]}
fmin(i) = min {fmin(i-1) * nums[i], nums[i] , fmax * nums[i]}
下面我们来看一下代码的实现。
class Solution:
def maxProduct(self,nums):
n=len(nums)
dp_max=nums[:]
dp_min=nums[:]
for i in range(1,n):
dp_max[i]=max(nums[i],dp_min[i-1] * nums[i],dp_max[i-1] * nums[i])
dp_min[i]=min(nums[i],dp_min[i-1] * nums[i],dp_max[i-1] * nums[i])
return max(dp_max)
该算法的时间复杂度和空间复杂度都是O(n)。由于第i个状态只有i-1的状态有关，所以我们不需要保存i-1之前的状态，因为我们只需要常数个变量就可以求解，如下所示。
class Solution:
def maxProduct(self,nums):
n=len(nums)
dpmax=nums[0]
dpmin=nums[0]
res=nums[0]
for i in range(1,n):
tmpmax=dpmax
tmpmin=dpmin
dpmax=max(nums[i], tmpmin * nums[i], tmpmax * nums[i])
dpmin=min(nums[i], tmpmin * nums[i], tmpmax * nums[i])
res=max(dpmax,res)
return res
该算法的时间复杂度是O(n)，空间复杂度是O(1)。
打家劫舍I
198. 打家劫舍
问题描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例：
输入：[1，2，3，1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
分析问题
首先，我们先将问题简化处理。假设目前只有一间房屋，则偷窃该房屋，此时就是偷窃到的最高总金额。如果只有两间房屋，因为此时两间房屋相邻，只能偷窃其中的一间房屋，可以选择其中金额较高的房屋进行偷窃，就是可以偷窃到的最高总金额。如果房屋的数量大于两间，假设小偷此时处于第k（k>2）间房屋，那么他有两个选择。
如果他偷窃第k间房屋，那么他就不能偷窃第k-1间房屋，此时其能偷窃到的总金额为前k-2间房屋的最高总金额和第k间房屋的金额之和。 如果他不偷窃第k间房屋，那么此时其能偷窃到的总金额为前k-1间房屋的最高总金额。
在上述两个选项中选择金额较大的即为前k间房屋能偷窃到的最高总金额。
我们用 dp[i] 来表示前 i 间房屋能偷窃到的最高总金额，经过前面的分析，可以知道其状态转移方程为：
下面我们来看一下边界条件。
当只有一间房屋时，此时dp[0] = nums[0]，表示偷窃该房屋。 当只有两间房屋时，此时 dp[1] = max(nums[0] , nums[1])，即在这两间房屋中选择金额较大的房屋进行偷窃。
下面我们来看一下代码的实现。
class Solution:
def rob(self, nums):
#如果数组为空，则直接返回0
if not nums:
return 0
length = len(nums)
#如果房屋数量等于1
#则直接偷窃第一间房屋，
#所以此时能偷窃到的最大金额是nums[0]
if length == 1:
return nums[0]
dp = [0] * length
#边界条件
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, length):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return dp[length - 1]
该算法的时间复杂度是O(n)，空间复杂度也是O(n)。
通过观察，我们发现dp[i] 只和 dp[i-2] 和 dp[i-1]有关，即只和该房屋的前两间房屋的最高总金额相关，所以我们可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额即可，从而降低空间复杂度。我们来看一下代码的实现。
class Solution:
def rob(self, nums):
#如果数组为空，则直接返回0
if not nums:
return 0
length = len(nums)
#如果房屋数量等于1
#则直接偷窃第一间房屋，
#所以此时能偷窃到的最大金额是nums[0]
if length == 1:
return nums[0]
#边界条件
first, second = nums[0], max(nums[0], nums[1])
for i in range(2, length):
first, second = second, max(first + nums[i], second)
return second
该算法的时间复杂度是O(n)，空间复杂度是O(1)。
打家劫舍II
213. 打家劫舍 II
问题描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
分析问题
这道题和上一道的不同之处在于房屋的首尾是相连的，即第一间房屋和最后一间房屋是相邻的，因此它们不能被同时偷窃。
我们也可以和上一道题的思路一样，采用动态规划的方法来求解。首先先将问题简单化，假设此时只有一间房屋，则偷窃该房屋，此时就是偷窃到的最高总金额。如果只有两间房屋，因为此时两间房屋相邻，只能偷窃其中的一间房屋，可以选择其中金额较高的房屋进行偷窃，就是可以偷窃到的最高总金额。
到这里我们可以注意到，当房屋数量不超过两间时，最多只能偷窃一间房屋，因此我们不需要考虑首尾连接的问题。但是，如果房屋数量大于二间时，就必须要考虑该限制条件了，即第一间房屋和最后一间房屋不能同时被偷窃。那么如何才能保证第一间房屋和最后一间房屋不能同时被偷窃呢？这里可以分情况来讨论。
如果偷窃了第一间房屋，那么就不能偷窃最后一间房屋，因此可以偷窃的房屋的范围是第一间房屋到倒数第二间房屋。 如果偷窃了最后一间房屋，那么就不能偷窃第一间房屋，因此可以偷窃的房屋的范围是第二间房屋到最后一间房屋。
我们假设数组 nums 的长度为n。如果不偷窃最后一间房屋，则可以偷窃的房屋的下标是0~n-2；如果不偷窃第一间房屋，则可以偷窃的房屋的下标是1~n-1。
接下来我们就可以采用上一题的解法，对于两段下标范围分别计算可以偷窃到的最高总金额，其中的最大值即为在 n 间房屋中可以偷窃到的最高总金额。
下面我们来看一下代码的实现。
class Solution:
def rob(self, nums):
#求nums[start,end]范围内可以偷窃到的最大金额
def help(start, end):
first = nums[start]
second = max(nums[start], nums[start + 1])
for i in range(start + 2, end + 1):
first, second = second, max(first + nums[i], second)
return second
length = len(nums)
#边界条件
if length == 1:
return nums[0]
elif length == 2:
return max(nums[0], nums[1])
else:
return max(help(0, length - 2), help(1, length - 1))
该算法的时间复杂度是O(n)，空间复杂度是O(1)。
打家劫舍III
337. 打家劫舍 III
问题描述
在上次打劫完一条街道和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父”房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
示例：
输入：[3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出：7
解释：小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7。
分析问题
首先我们把该问题转化一下，该问题其实是求：对于一棵二叉树来说，树上的每个点都有对应的权值，并且每个点有两种状态（选中和不选中），在不能同时选中有父子关系的点的情况下，能选中的点的最大权值和是多少。
首先我们用f(a)来表示选择a节点的情况下，a节点的子树上被选择的节点的最大权值和。g(a)表示在不选择a节点的情况下，a节点的子树上被选择的节点的最大权值和。l 和 r 分别表示a的左右孩子。
小偷对于树中的每个节点都有偷或者不偷两种选择，假设当前的节点是a。
当a被选中时，a的左右孩子都不能被选中，所以a被选中的情况下，它的子树上被选择的节点的最大权值和为l 和 r 不被选中的最大权值和相加，即 f(a) = g(l) + g(r)。 当a不被选中时，a的左右孩子可以被选中，也可以不被选中。此时 g(a) = max { f(l) , g(l) } + max{ f(r) , g(r) }。
这里我们可以使用深度优先搜索的办法后序遍历这棵二叉树，就可以得到每一个节点的 f 和 g。根节点的 f和 g 的最大值就是我们要找的答案。
下面我们来看一下代码的实现。
class Solution:
def __init__(self):
self.f={}
self.g={}
def dfs(self,node):
if not node:
return
self.dfs(node.left)
self.dfs(node.right)
#表示选中该节点
self.f[node]=node.val + self.g.get(node.left,0) + self.g.get(node.right,0)
#表示没有选择该节点
self.g[node] = max(self.f.get(node.left,0),self.g.get(node.left,0)) \
+ max(self.f.get(node.right,0),self.g.get(node.right,0))
def rob(self, root):
self.dfs(root)
return max(self.f.get(root,0),self.g.get(root,0))
该算法的时间复杂度是O(n)，空间复杂度也是O(n)。
这里我们还可以优化一下，因为无论是求 f(a) 还是 g(a)，他们的值只和 f(l) 、g(l)、f(r)和g(r)有关。所以对于每一个节点，我们只关心它的左右孩子的 f 和 g 是多少。在python中，我们可以用元组来表示，每次递归返回的时候，都把这个点对应的 f 和 g 返回给上一级调用。这样我们就可以省去哈希表的空间，下面我们来看一下具体的代码实现。
class Solution:
def dfs(self,node):
if not node:
return (0,0)
left=self.dfs(node.left)
right=self.dfs(node.right)
#表示选中该节点
selected = node.val + left[1] + right[1]
#表示没有选择该节点
noselected = max(left[0],left[1]) \
+ max(right[0],right[1])
return (selected,noselected)
def rob(self, root):
result=self.dfs(root)
return max(result[0],result[1])
该算法的时间复杂度是O(n)，空间复杂度也是O(n)。
原创不易！各位小伙伴觉得文章不错的话，不妨点赞（在看）、留言、转发三连走起！
欢迎关注公众号 程序员学长，助你少走弯路进大厂。
你知道的越多，你的思维越开阔。我们下期再见。