动态规划三要素：
最优子结构：子问题 会影响 父问题的最优解
// 注意子问题影响，而不是子问题的解影响，
// 当然有些问题是子问题的解影响父问题的解，我想说的是不全是解和解得关系，子问题的最优解和父问题的最优解可能毫无关系
状态转移：根据子问题 如何推出 父问题的解，递推关系式
边界问题：最小子问题的解是否已知
爬楼梯
'''
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
分析:
假定n=10,首先考虑最后一步的情况,要么从第九级台阶再走一级到第十级,要么从第八级台阶走两级到第十级,因而,要想到达第十级台阶,最后一步一定是从第八级或者第九级台阶开始.也就是说已知从地面到第八级台阶一共有X种走法,从地面到第九级台阶一共有Y种走法,那么从地面到第十级台阶一共有X+Y种走法.
即F(10)=F(9)+F(8)
分析到这里,动态规划的三要素出来了.
边界:F(1)=1,F(2)=2
最优子结构:F(10)的最优子结构即F(9)和F(8)
状态转移函数:F(n)=F(n-1)+F(n-2)
'''
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n<=2:
return n
a=1 #边界
b=2 #边界
temp=0
for i in range(3,n+1):
temp=a+b #状态转移
a=b #最优子结构
b=temp #最优子结构
return temp
print(Solution().climbStairs(10))
小偷偷东西
'''
一个小偷准备挨家挨户进行偷窃，每一家都有一些能偷到的金额值，但是不能连续进入相邻的两间房屋，否则会被发现。
将这个设定抽象成一个数组，每家拥有的金额组成一个非负的整型数组，在不被发现的情况下，计算小偷能偷到的最大数额。
例如[1,2,5,3,4,8,2]，那么最大值就是：第一家（1）+第三家（5）+第六家（8）=14.
最优子结构：最后一家偷不偷，偷则加上前两位的最大值，不偷则是前一位的最大值
边界：d[0]=nums[0], d[1]=max(nums[0], nums[1])
状态转移函数:d[i]=max(d[i-1], d[i-2]+nums[i])
'''
class Solution(object):
def rob(self, nums):
if len(nums)==0:
return 0
if len(nums)<=2:
return max(nums)
dp = []
dp.append(nums[0])
dp.append(max(nums[0], nums[1]))
for i in range(2, len(nums)):
dp.append(max(dp[i-1], dp[i-2]+nums[i]))
return dp[-1]
if __name__ == '__main__':
nums = [1,2,5,3,4,8,2]
print(Solution().rob(nums))
最小花费爬楼梯
'''
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
最优子结构：f(9)和f(8)
边界：f(0)=1, f(1)=100
递推式：f(10)=min(f(9)+cost(9), f(8)+cost(8))
'''
class Solution(object):
def minCostClimbingStairs(self, cost):
if len(cost) <= 1:
return min(cost)
dp = []
dp.append(cost[0])
dp.append(cost[1])
for i in range(2, len(cost)+1):
if i==len(cost):
dp.append(min(dp[i-1], dp[i-2]))
else:
dp.append(min(dp[i-1]+cost[i], dp[i-2]+cost[i]))
return dp[-1]
最大和子序列
这个问题还是挺难的，很多教程并没有 彻彻底底 讲清楚逻辑，我思考了很久才得出下图
'''
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6
'''
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
nums = [-2, -1, -3, 4, -1, 2, 1, -5, 4]
dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5]
# nums = [-2, 1, -3]
# nums = [1, -5, 2]
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 判断边界
if len(nums) == 0:
return 0
d = [] # 定义一个表格进行存储上一个子问题的最优解
d.append(nums[0]) # 第一个最优解为第一个元素
max_ = nums[0] # 返回的最大值
for i in range(1, len(nums)):
if nums[i] > nums[i] + d[i - 1]:
d.append(nums[i])
else:
d.append(nums[i] + d[i - 1])
print(d)
if max_ < d[i]:
max_ = d[i]
return max_
print(Solution().maxSubArray(nums))
参考资料：