1. 动态规划框架

• 核心:穷举求最值
• 动态规划特点:
  • 重叠子问题
  • 状态转移方程（最关键）
  • 最优子结构
• 解题套路:
  • 明确状态
  • 明确选择
  • 明确dp函数/数组的定义
  • 明确base case
• DP解法代码框架:

# 1.创建base case
dp[0][0][...] = base
# 2.初始化base case
# 3.穷举状态
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
            # 4.状态转移
            dp[状态1][状态2][...] = 求最值(选择1,选择2...)

2. 斐波那契数

class Solution:
    # 最优解法：最终优化空间复杂度(% 1000000007防越界)
    def fib(n):
        i,j = 0,1
        for _ in range(n):
            i, j = j, i + j
        return i % 1000000007
    # 基础递归
    def fib(n):
        if n == 0 or n == 1: return n
        return fib(n-1) + fib(n-2)
    # 递归优化
    def fib(n):
        # 递归剪枝：将计算过的节点存起来，空间换时间
        _dict = [0 for i in range(n+1)]
        # 递归方法
        def rec(n):
            if n == 0 or n == 1: return n
            if _dict[n] != 0: return _dict[n]
            _dict[n] = rec(n-1) + rec(n-2)
            return _dict[n]
        return rec(n)
    # 动态规划（自顶向下）
    def fib(n):
        if n == 0: return 0
        dp = [0 for i in range(n+1)]
        dp[0], dp[1] = 0, 1
        for i in range(2,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]
    # 最优解法：优化空间复杂度
    def fib(n):
        i,j = 0,1
        for _ in range(n):
            i, j = j, i + j
        return i
# UT
print(Solution().fib(7))

3. 青蛙台阶

# 一次可以跳1阶/2阶
class Solution:
    def numWays(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a % 1000000007

4. 最长公共子串

def longestCommonString(self, A: str, B: str) -> int:
    # 因为需要遍历字符串并构建存储矩阵，所以需要求两个字符串的长度
    m, n = len(A), len(B)
    # 初始化为0的存储矩阵，dp[i][j]用于存储该‘单元’之前的子串长度
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    # 初始化最终结果，长度为整型，默认为0
    ans = 0
    # 因为需要判断子问题，所以i，j以1而不是0开始，结束也是对应的m+1和n+1
    # （实质遍历的是存储单元，与字符串遍历相差为1）
    # 对于字符串，m+1，n+1指针是越界的，但是对于存储，是不越界的。
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # 通过子问题判断，来决定当前的d[i][j]的值
            # d[i][j]存储的就是之间累加的子串长度
            if A[i - 1] == B[j - 1]:
                # 如果两个字符串的当前字符相等，那么dp[i][j]的值就是之前d[i-1][j-1]存储的长度+1
                dp[i][j] = dp[i - 1][j - 1] + 1
                # 新得到的最长序列要和上一次得到的最长序列结果ans取最大成为新的ans
                ans = max(ans, dp[i][j])
            # 此处不需要else：与公共子序列相比不需要考虑字符不相同的情况，不相同直接从0计数
    return ans
# UT
a, b = 'abcdef','abf'
print(longestCommonString(a, b))

- 与子序列相比，子串只是不去考虑双重循环中，条件语句中的else
- 因为默认矩阵为0，即如果A[i - 1] != B[j - 1]即出现不连续，那么从0开始重新计数
- 而子序列却需要从附近的存储单元来延续这个数值

5. 最长公共子序列

def longestCommonSubsequence(a: str, b: str) -> int:
    m, n = len(a), len(b)
    dp = [[0 for _ in range(n + 1)] for __ in range(m + 1)]
    ans = 0
    for i in range(1, m + 1):  # 规划表 外层
        for j in range(1, n + 1):  # 规划表 内层
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                ans = max(ans, dp[i][j])
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return ans
# UT
a, b = 'abcdef','abf'
print(longestCommonSubsequence(a, b))

6. 零钱兑换

from typing import List
import sys
# 暴力递归
def coinChange(coins:List[int],amount:int):
    # base case
    if amount == 0 : return 0
    if amount < 0: return -1

    res = sys.maxsize
    for i in coins:
        tmp = coinChange(coins,amount-i)
        if tmp == -1: continue
        res = min(res,tmp+1)
    return res == sys.maxsize and -1 or res

# 递归优化（自顶向下递归）
def coinChange(coins:List[int],amount:int):
    _dict = [ -1000 for i in range(amount+1)]
    def dp(coins:List[int],amount:int):
        if amount == 0: return 0
        if amount < 0: return -1
        # 优化关键点
        if _dict[amount] != -1000:
            return _dict[amount]
        # 计算子问题
        res = sys.maxsize
        for i in coins:
            tmp = dp(coins,amount-i)
            if tmp == -1: continue
            res = min(res,tmp+1)

        _dict[amount] = res == sys.maxsize and -1 or res
        return _dict[amount]

    return dp(coins,amount)
# 动态规划：自底向上迭代解法
def coinChange(coins:List[int],amount:int):
    dp = [amount+1 for i in range(amount+1)]
    print(dp)
    dp[0] = 0
    for i in range(amount+1):
        for coin in coins:
            if i - coin < 0: continue
            dp[i] = min(dp[i],1+dp[i-coin])
    return dp[amount] == amount + 1 and -1 or dp[amount]

print(coinChange([1,2,5],11))

7. 编辑距离

class Solution:
    # 方法一：递归
    def edit_distance_rec(self, word1: str, word2: str) -> int:
        l1,l2 = len(word1),len(word2)
        if l1 == 0 or l2 == 0 :
            return max(l1,l2)
        if word1[l1-1] == word2[l2-1]:
            return self.edit_distance_rec(word1[0:-1], word2[0:-1])
        else:
            return min([
                self.edit_distance_rec(word1[:-1], word2),
                self.edit_distance_rec(word1, word2[:-1]),
                self.edit_distance_rec(word1[:-1], word2[:-1])
                ]) + 1
    # 方法二：动态规划
    def edit_distance_dp(self, word1: str, word2: str) -> int:
        n = len(word1)
        m = len(word2)
        # 有一个字符串为空串
        if n * m == 0:
            return n + m
        # DP 数组
        D = [ [0] * (m + 1) for _ in range(n + 1)]
        # 边界状态初始化：base case
        for i in range(n + 1):
            D[i][0] = i
        for j in range(m + 1):
            D[0][j] = j
        # 计算所有 DP 值：穷举状态
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                left = D[i - 1][j] + 1
                down = D[i][j - 1] + 1
                left_down = D[i - 1][j - 1]
                # 状态转移
                if word1[i - 1] != word2[j - 1]:
                    left_down += 1
                D[i][j] = min(left, down, left_down)

        return D[n][m]
#UT
w1,w2 = "banbana","baa"
print(Solution().edit_distance_rec(w1,w2))
print(Solution().edit_distance_dp(w1,w2))

8. 机器人(0,0)到(x,y)走法

# 0,0到x,y所有走法（下、右）
# 1.暴力递归
def recursion(x, y):
    if x == 1 or y == 1:
        return 1
    x, y = abs(x), abs(y)
    return recursion(x-1, y) + recursion(x, y-1)

# 2.dp动态规划
def dp_func(x, y):
    """
    dp[i][0] = 1 for i = 0,...,x-1
    dp[0][j] = 1 for j = 0,...,y-1
    dp[x][y] = dp[x-1][y] + dp[x][y-1]
    """
    if x == 0 and y == 0:
        return 0
    if x == 0 or y == 0:
        return 1
    x, y = abs(x), abs(y)
    dp = [[0 for _ in range(y)] for _ in range(x)]
    for i in range(x):
        dp[i][0] = 1
    for i in range(y):
        dp[0][i] = 1
    for i in range(1, x):
        for j in range(1, y):
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
    return dp[x-1][y-1]

def dp_func2(x,y):
    dp = [1 for _ in range(x)]
    for i in range(1,x):
        for j in range(1,y):
            dp[j] += dp[j-1]
    return dp[y-1]

print(recursion(4,4))
print(dp_func(4,4))
print(dp_func2(4,4))