动态规划【算法】

1. 基本结构

1.1 介绍

动态规划(dynamic programming) 是运筹学的一个分支,是求解决策过程(decision process)中最优化的数学方法。

  • 起源:在研究多阶段决策过程(multi-step decision process)的优化问题时,提出的最优性原理(principle of optimality),把多阶段过程转化为单阶段问题,逐个求解。
  • 应用领域:经济管理、生产调度、工程技术和最优控制。
  • 局限:主要是用于求解“分阶段”的动态过程的优化问题。
  • 经典问题:背包问题
  • 比较:
    • 贪婪:永远局部最优
    • 递归:重复计算
    • DP:记录局部最优子结构/多种记录值

1.2 基本概念

  • 阶段step:它是对整个过程的划分,通常会根据时间或者空间顺序进行分阶段。
  • 状态state:它表示每个阶段开始时过程所处的自然状况,它描述了过程的特征并且无后效性。
    • 无后效应:与之前的状态无关。
    • 状体变量state variable:用于描述状态的变量。
  • 决策decision:当一个阶段状态确定后,可以作出各种选择从而演变到下一阶段的某种状态,称为决策。
  • 策略 policy:决策组成的序列称为策略。
  • 状态转移方程 equation of state transition :用于描述某阶段的状态和决策与下阶段状态的关系。

1.3 基本思想— 多阶段决策。

1.4 实现步骤

  1. 递推 / 递归+记忆性
  2. 状态的定义:opt[n]
  3. 状态转移方程:opt[n] = best_of{opt[n-1],opt[n-2],…}
  4. 最优子结构

  5. 常见面试题

2. 常见面试题

2.1 选数

有一堆整数,选其中两两不相邻的数,使得合最大。

C = (1,2,3,1,1,5,7,6) ,len(C)=8。

  1. 可以考虑使用递归的思想

    1. 针对opt(8)

      • 若选C8,则需要从前6个数中找到最大的。
      • 若不选,则在前7个数中找到最大。
    2. 针对opt(7)

      • 若选C7,则需要在前5个中找到最大的。
      • 若不选,则需要在前6个中找到最大。

      ….

    3. 针对opt(1)

      • 若选1,opt(1) = 1
      • 若不选, 则opt(0) = 0
  2. 递推公式

  3. 编写代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    # encoding = utf-8
    c = [1, 2, 3, 1, 1, 5, 7, 6]
    data = dict() # 用于储存opt数据
    index = dict() # 用于储存索引

    def opt(i):
    if i in data:
    return data[i]
    else:
    if i < 0:
    return 0
    elif i == 0 or i == 1:
    index[i] = [i]
    return c[i]
    else:
    if c[i] + opt(i - 2) >= opt(i - 1):
    res = c[i]+opt(i-2)
    index[i] = [i]+index[i-2]
    else:
    res = opt(i-1)
    index[i] = index[i-1]
    data[i] = res
    return res

    for i in range(len(c)):
    print(opt(i))

    print(index)

2.2 换零钱

换零钱,有6元,有硬币为d=(1,3,4)两种硬币,问至少要换多少枚硬币。

  1. 考虑递归思想

    6元,可以换1+5,3+3;4+2;

    5元,可以换1+4,3+2;4+1;

    1元,可以换1。

    • 公式表达递归
  • 回溯
  1. 递推公式

    • 通式
  • 实例
  1. 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution:
    def coinChange(self, coins, amount):
    # 初始化
    MAX = float('inf')
    obj = [0] + [MAX] * amount
    for i in range(1, amount+1):
    # 递推公式:
    # 遍历 (钱-硬币)中所有大于0的可能值中最小的。
    obj[i] = min([obj[i - coin] if i - coin >= 0 else MAX for coin in coins])+1
    return -1 if obj[-1] == float('inf') else obj[-1]

2.3 找路

从开始点(0,0)走到(8,8)有多少种走法?只能向下或者向右。

  1. 考虑递归思想,考虑从Start>>End有多少种路

    1. paths(Start,End) = paths(A,End)+paths(B,End)

    2. paths(A,End) = paths(C,End)+paths(D,End)

    3. paths(B,End)) = paths(C,End)+paths(E,End)

      ….

  1. 递推公式

从End出发,计算它下方和右方的路径和,就是到达此点的路径数,如下图所示。

  1. 代码
1
2
3
4
5
# 核心代码
if a[i,j] == "空地":
opt[i,j] = opt[i-1,j] + opt[i,j-1]
else:
opt[i,j] = 0 # 此处为石头,边界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# encoding = utf-8
data = [[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 1, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 1, 0],
[0, 1, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]


width = len(data[0])
height = len(data)
# 0. 建立数组用于保存整张图的次数
num = [[0 for i in range(width)] for j in range(height)]

# 1. 嵌套循环,遍历整个图
for i in range(width):
for j in range(height):
# 2.1 初始化开始位置
if i == 0 and j == 0:
num[i][j] = 1
else:
# 2.2 当是石头,直接为0
if data[i][j] == 1:
num[i][j] = 0
else:
# 2.3 当不是石头时
# 2.3.1 考虑两个边的情况
if i < 0:
num[i][j] = 0 + num[i][j-1]
elif j < 0:
num[i][j] = num[i-1][j] + 0
# 2.3.1 递推式
else:
num[i][j] = num[i-1][j] + num[i][j-1]

for i in range(width):
for j in range(height):
print(str(num[i][j])+" ", end="")
print("")

2.4 爬楼梯

简单解释一下,就是上x层楼梯,有多少种走法?

  1. 直接写递推公式了。

  2. 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # encoding = utf-8
    class Solution:
    def climbStairs(self, n):
    if n < 3:
    return n
    else:
    step_stair = [0 for i in range(n+1)] # 初始化数组,用于保存每一步的可能性
    step_stair[1], step_stair[2] = 1, 2 # 初始化,前两层台阶
    for i in range(3, n+1):
    step_stair[i] = step_stair[i - 1] + step_stair[i - 2]
    return step_stair[n] # 返回第n阶台阶的可能性

    S = Solution()
    print(S.climbStairs(10))

2.5 三角形的最小路径和

给定一个三角形,找到从上到下的最小路径总和。 您可以移动到下面一行中相邻数字的每一步。

  1. 递推公式(m表示有m行)
  2. 举例说明:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    data = [[2],
    [3,4],
    [6,5,7],
    [4,1,8,3]]
    opt[3] = [4,1,8,3]
    opt[2] = [6+min{4,1},5+min{1,8},7+min{8,3}]=[7,6,10]
    opt[1] = [3+min{7,6},4+{6,10}]=[9,10]
    opt[0] = [2+min{9,10}]=[11]
    out=11
  3. 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution:
    def minimumTotal(self, triangle):
    if not triangle:
    return 0
    obj = triangle[-1]
    for i in range(len(triangle)-2, -1, -1): # 从倒数第二行开始遍历 i 表示行
    for j in range(len(triangle[i])): # j表示列
    obj[j] = triangle[i][j] + min(obj[j], obj[j+1])
    return obj[0]

    if __name__ == '__main__':
    data = [[-1],
    [2, 3],
    [1, -1, -3]]
    S = Solution()
    out = S.minimumTotal(data)
    print(out)

2.6 乘积最大子序列

给定整数数组,找到具有最大乘积的数组(包含至少一个数字)内的连续子数组。

1
2
3
4
5
6
7
8
9
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
  1. 分析

    每次循环中,判断,最小值,最大值与当前数的大小。

  2. 递推公式

    1
    2
    3
    4
    5
    6
    7
    nums = [2,3,-2,4]
    Init: res=2,curMax=2,curMin=2
    Loop:
    num=3,curMax=2*3=6, curMin=2*3=6 >>{3,6,6} curMax=6,curMin=3,res=6
    num=-2,curMax=6*-2=-12,curMin=3*-2=-6 >>{-2,-6,-12} curMax=-2,curMin=-12,res=6
    num=4,curMax=-2*4=-8,curMin=-12*4=-48 >>{4,-8,-48} curMax=4,curMin=-48,res=6
    return res=-6
  3. 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution:
    def maxProduct(self, nums):
    if nums is None:
    return 0
    res, curMax , curMin = nums[0], nums[0], nums[0]
    for i in range(1,len(nums)):
    num = nums[i]
    curMax, curMin = curMax*num, curMin*num
    curMin, curMax = min(curMax, curMin, num), max(curMax, curMin, num)
    res = curMax if curMax > res else res
    return res

2.7 股票买卖系列

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

2.8 最长上升子序列

待补充

2.9 编辑距离

待补充