# ===== CodeLab: 动态规划入门 =====
# 来源: https://aoerliang.dpdns.org/articles/algo-dp
# 以下代码片段按文章出现顺序拼接, 共 4 段

# ----- 片段 1 (python) -----
# 自底向上:从最小子问题开始,一步步推到大问题
def fib_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fib_dp(50))   # 12586269025,瞬间完成

# ----- 片段 2 (python) -----
def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(climb_stairs(3))   # 3: (1,1,1) (1,2) (2,1)

# ----- 片段 3 (python) -----
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

print(unique_paths(3, 3))  # 6
print(unique_paths(3, 7))  # 28

# ----- 片段 4 (python) -----
def knapsack(W, weights, values):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for j in range(W, w - 1, -1):   # 倒序,防止重复取
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[W]

W = 5
print(knapsack(W, [2, 1, 3], [4, 2, 3]))  # 6: 选 1 号 + 2 号