动态规划入门
动态规划(Dynamic programming, 简称DP), 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
DP常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所消耗的时间往往远小于朴素解法。
1. 基本思想与策略
基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
一言以蔽之：大事化小，小事化了。
分治与动态规划
共同点：两者都要求原问题具有最优子结构性质，都是将原问题分而治之，分解成若干个规模较小的子问题，然后将子问题的解合并，最终得到答案。
不同点：分治法将分解后的子问题看成相互独立的，通常用递归来做。动态规划将分解后的子问题理解为相互间有联系，有重叠部分，需要记忆，通常用迭代来做。
2. 使用的情况
能采用动态规划求解的问题通常要具备３个性质：
- 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理
- 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
- 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
3. 求解的基本步骤
动态规划的设计都有一定的模式，一般要经历一下几个步骤。
初始状态-->|决策１|-->|决策２|-->...-->|决策Ｎ|-->结束状态
划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
-
寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。
实际应用中可以按以下几个简化的步骤进行设计：
（1）分析最优解的性质，并刻画其结构特征。
（2）递归的定义最优解。
（3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
（4）根据计算最优值时得到的信息，构造问题的最优解
参考流程：
递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法
4. 举例
例１：斐波那契数列
暴力的递归算法
时间复杂度:O(2^n)
class Solution:
def fib(self, N: int):
if N <= 1:
return N
return self.fib(N-1) + self.fib(N-2)
观察递归树，很明显发现算法低效的原因：存在大量重复计算，如Ｆ(18）被计算了两遍。
带备忘录的递归算法
class Solution:
def fib(self, N: int) -> int:
if N <= 1:
return N
self.cache = {0: 0, 1: 1}
return self.memoize(N)
def memoize(self, N: int) -> {}:
if N in self.cache.keys():
return self.cache[N]
self.cache[N] = self.memoize(N-1) + self.memoize(N-2)
return self.memoize(N)
动态规划的递归算法
class Solution2: # 动态规划
def fib(self, N: int) -> int:
if N == 0:
return 0
a, b = 0, 1
for _ in range(2, N+1):
a, b = b, a+b
return b
动态转移方程
DP问题最困难的就是写出状态转移方程，即这个暴力解。优化方法无非是用备忘录或者 DP table，再无奥妙可言。
例2：凑零钱问题
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:输入: coins = [2], amount = 3
输出: -1说明:
你可以认为每种硬币的数量是无限的。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
状态转移方程
递归方法
根据状态转移方程写代码：
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if amount == 0:
return 0
ans = float('inf')
for coin in coins:
# 金额不可达
if amount - coin < 0:
continue
subProb = self.coinChange(coins, amount - coin)
# 子问题无解
if subProb == -1:
continue
ans = min(ans, subProb + 1)
return ans if ans != float('inf') else -1
带备忘录的递归算法
class Solution3(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
memo = {0: 0}
def helper(n):
if n in memo:
return memo[n]
res = float("inf")
for coin in coins:
if n >= coin:
res = min(res, helper(n - coin) + 1)
memo[n] = res
return res
return helper(amount) if (helper(amount) != float("inf")) else -1
动态规划
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp=[float("inf")]*(amount+1)
dp[0]=0
for i in range(1,amount+1):
for coin in coins:
if(i>=coin):
dp[i]=min(dp[i],dp[i-coin]+1)
return dp[-1] if(dp[-1]!=float("inf")) else -1
5. LeetCode
64. 最小路径和
题目描述
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
解题思路
二维动态规划:
分情况：
- 空矩阵
- 只有1行
- 只有1列
- 左边和上边都是矩阵边界
不需要建立DP矩阵，直接遍历grid[i][j]修改即可
代码实现
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
for i in range(len(grid)): # 共i行
for j in range(len(grid[0])): # 共j列
if i == j == 0:
continue
elif i == 0:
grid[i][j] = grid[i][j-1] + grid[i][j]
elif j == 0:
grid[i][j] = grid[i-1][j] + grid[i][j]
else:
grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
return grid[-1][-1]
70. 爬楼梯
题目描述
假设你正在爬楼梯。需要 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 阶来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
解题思路
一维动态规划
易得DP数组公式：
dp[i] =dp[i-1]+dp[i-2]
DP数组也可以省略
代码实现
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 0:
return 0
res,last = 1,1
for _ in range(1,n):
res,last = res+last,res
return res
121. 买卖股票的最佳时机
题目描述
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
解题思路
变量buying_price记录买入价，一旦遇到更低的买入价则更新此变量，使用max_profit记录可获得的最大收益，当收益更高是更新max_profit
代码实现
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
max_profits = 0
buying_price = prices[0]
for i in range(len(prices)):
if prices[i]<buying_price:
buying_price = prices[i]
else:
profit = prices[i] - buying_price
if profit>max_profits:
max_profits = profit
return max_profits
198. 打家劫舍
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber
解题思路
动态规划方程：
dp[n] = MAX( dp[n-1], dp[n-2] + num )
由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可盗窃的最大值，要么就是 n-1 房屋可盗窃的最大值，要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值
代码实现
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 0: return 0
dp = [0] * (n + 1)
dp[1] = nums[0]
for i in range(2,n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
return dp[-1]
