理解数学思想：动态规划(Dynamic Programming)

什么是动态规划

• 在给定约束条件下，优化某指标。
• 一个问题可以不断分解为一个个子问题，并且这些子问题是独立的。
• 和排列组合有所不同：我们只关心最优解，因此我们只保留每个子问题的最优解，每个问题的最优解都可以由之前的问题的最优解决定。所以效率较高。
• 关键是使用状态转移表来找到状态转移方程：每种动态规划的解决方案都需要画网格（状态转移表）来观察，每个单元格都是一个子问题，单元格的值通常就是要优化的值。通过单元格，找出每个单元格最优解与其他单元格最优解之间的关系。

应用

• 一个问题有多种可能，看上去要使用排列组合的思想。但其实只需要求最优解(比如，最大值、最小值、最短子串、最长字串等)。
• 生物/医学：使用最长公共序列来确定DNA链的相似性，进而判断两种生物和疾病的相似性
• 工具：git diff
• 查询推荐：字符串比较/编辑距离

实例

背包问题

求两个字符串的编辑距离（Edit Distance）：

• 上代码

import numpy as np
def get_str_distance(a,b):
    if a is None or b is None:
        return -1
    state_transfer_table = np.full((len(a)+1,len(b)+1),-1) # 状态转移表，是一个二维数组
    

    for i in range(len(a)+1):
        state_transfer_table[i][0] = i

    for j in range(len(b)+1):
        state_transfer_table[0][j] = j
    
#     print(state_transfer_table)
    for i in range(len(a)):
        for j in range(len(b)):
            r = 1 if a[i]!=b[j] else 0
            a_append = state_transfer_table[i][j+1]+1
            b_append = state_transfer_table[i+1][j]+1
            replace = state_transfer_table[i][j]+r
            state_transfer_table[i+1,j+1] = min(a_append,b_append,replace)
#             print(state_transfer_table)
    print(state_transfer_table)
    return state_transfer_table[len(a)][len(b)]

a = get_str_distance("guanpei","guan0peokk")
print(a)