本质是求 最优解！
解决最优化问题 optimization problems ！也就是说从多个可行解中找出最优的。
动态规划求解
划分阶段
按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
确定状态和状态变量
将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程
因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。
寻找边界条件
给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
求最优解的一般流程
实际上，任何的动态规划问题都可以通过添加一个「back 数组」的方法，来求出最优解的具体方案。我们可以仿照原先的「动态规划四步骤」，总结出求最优解的具体方案的步骤流程：
- 定义子问题
- 写出子问题的递推关系
- 确定 DP 数组的计算顺序
- 按顺序计算 DP 数组与 back 数组
- 从最后的子问题出发，根据 back 数组回退，得到最优解的具体方案
需要注意的是，以上步骤并不包括「空间优化」。如果想求出最优解的具体方案的话，是不能进行空间优化的，否则会丢失一些必要的信息。
例： 打家劫舍问题
动态规划题目总结
面试题 08.11. 硬币
给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
示例1:
输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
class Solution:
def waysToChange(self, n: int) -> int:
coins = [1, 5, 10, 25]
dp = [0] * (n + 1)
dp[0] = 1
for coin in coins :
for i in range(coin, n + 1) :
dp[i] = dp[i] + dp[i - coin]
return dp[n] % 1000000007
LEETCODE-1248. 统计「优美子数组」
264. 丑数 II
编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
1 是丑数。n 不超过1690。输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
class Solution:
def nthUglyNumber(self, n: int) -> int:
dp = [1 for _ in range(n)]
# 三指针初始化
i2 = 0
i3 = 0
i5 = 0
for i in range(1,n):
min_val = min(dp[i2]*2,dp[i3]*3,dp[i5]*5)
dp[i] = min_val
# 找出哪个指针对应的数造出了现在这个最小值，将指针前移一位
if dp[i2]*2 == min_val:
i2 += 1
if dp[i3]*3 == min_val:
i3 += 1
if dp[i5]*5 == min_val:
i5 += 1
return dp[-1]
221. 最大正方形
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出:
4
- 特例： 空矩阵直接返回 0
- 每个正方形的右下角必为 1
- 设
dp[i][j]为以 i 行 j 列点为右下角的正方形的最大的边长
则有：dp[i][j] = min(dp[i−1][j−1], dp[i−1][j], dp[i][j−1]) + 1 - 初始化：(i_len+1)∗(j_len+1) 的 dp 二维矩阵， 全0
多一行在左边和上边，这样可以防止越界，简化判定 - 遍历：
i in range(1, i_len + 1)，j in range(1, j_len + 1)
如果matrix[i−1][j−1] == 1可能有正方形存在
dp[i][j] = min(dp[i−1][j−1], dp[i−1][j], dp[i][j−1]) + 1
每次循环更新最大边长
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix:
return 0
i_len = len(matrix)
j_len = len(matrix[0])
side_length = 0
dp = [[0]* (j_len+1) for i in range(i_len+1)]
for i in range(1, 1+i_len):
for j in range(1, 1+j_len):
if matrix[i-1][j-1] == '1':
dp[i][j] = min( dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
side_length = max(dp[i][j],side_length)
return side_length * side_length
网友评论