02_动态规划

动态规划

# ===== 1. 背包问题 =====
# 01 背包（每个物品选0或1次）
def knapsack_01(n, W, weights, values):
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):  # 倒序遍历
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# 完全背包（每个物品可选无限次）
def knapsack_complete(n, W, weights, values):
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(weights[i], W + 1):  # 正序遍历
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# 多重背包（每个物品可选有限次）- 二进制优化
def knapsack_multi(n, W, weights, values, counts):
    items = []  # 转化为01背包
    for i in range(n):
        k = 1
        c = counts[i]
        while c > 0:
            take = min(k, c)
            items.append((weights[i] * take, values[i] * take))
            c -= take
            k *= 2
    dp = [0] * (W + 1)
    for w, v in items:
        for j in range(W, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[W]

# ===== 计数DP（爬楼梯/骰子问题）=====
# 每次可以走1~k步，求到达n级台阶的走法数
def count_ways(n, k):
    dp = [0] * (n + 1)
    dp[0] = 1  # 基础情况：到达0级只有1种方式（不走）
    for i in range(1, n + 1):
        dp[i] = sum(dp[max(0, i-k):i]) % MOD
    return dp[n]

# 简化为：每次走1~6步（骰子问题）
dp = [1]
for i in range(int(input())):
    dp.append(sum(dp[-6:]) % MOD)
print(dp[-1])

# ===== 2. 最长上升子序列 (LIS) =====
def lis(arr):
    import bisect
    dp = []
    for x in arr:
        pos = bisect.bisect_left(dp, x)
        if pos == len(dp):
            dp.append(x)
        else:
            dp[pos] = x
    return len(dp)

# ===== 3. 最长公共子序列 (LCS) =====
def lcs(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

# ===== 4. 编辑距离 =====
def edit_distance(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = i
    for j in range(m+1):
        dp[0][j] = j
    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[n][m]

# ===== 5. 区间 DP =====
def interval_dp(n, cost):
    # dp[i][j] = 合并 i~j 的最小代价
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            dp[i][j] = min(dp[i][k] + dp[k+1][j] for k in range(i, j))
    return dp[0][n-1]