动态规划

背包DP

• 0-1背包

  def knapsack(capacity, weights, values):
      dp = [0] * (capacity + 1)
      for i in range(len(weights)):
          weight = weights[i]
          value = values[i]
          # 倒序遍历确保每个物品只选一次
          for j in range(capacity, weight - 1, -1):
              dp[j] = max(dp[j], dp[j - weight] + value)
      return dp[-1]

• 多重背包

  def knapsack_multiple(capacity, weights, values, counts):
      dp = [0] * (capacity + 1)
      for i in range(len(weights)):
          weight = weights[i]
          value = values[i]
          count = counts[i]
          for j in range(capacity, weight - 1, -1):
              for k in range(1, count + 1):
                  if weight * k > j:
                      break
                  dp[j] = max(dp[j], dp[j - weight * k] + value * k)
      return dp[-1]

  def knapsack_multiple(capacity, weights, values, counts):
      dp = [0] * (capacity + 1)
      for i in range(len(weights)):
          weight = weights[i]
          value = values[i]
          count = counts[i]
          k = 1
          while k < count:
              # 二进制拆分：将当前k个物品视为01背包的子物品
              for j in range(capacity, weight * k - 1, -1):
                  dp[j] = max(dp[j], dp[j - weight * k] + value * k)
              count -= k
              k *= 2
          # 处理剩余无法拆分的cnt个物品
          if count > 0:
              for j in range(capacity, weight * count - 1, -1):
                  dp[j] = max(dp[j], dp[j - weight * count] + value * count)
      return dp[-1]

• 完全背包

  def knapsack_complete(capacity, weights, values):
      dp = [0] * (capacity + 1)
      for i in range(len(weights)):
          weight = weights[i]
          value = values[i]
          
          # 正序遍历允许重复选择当前物品
          for j in range(weight, capacity + 1):
              dp[j] = max(dp[j], dp[j - weight] + value)

• 混合背包
  通过组合0-1背包、多重背包和完全背包实现

• 状态压缩
  capacity和weights除以最大公约数作为新的容量和重量。

区间DP

树形DP

• 树上背包

def dfs(i):
    weight = weights[i]
    value = values[i]
    dp = [0] * (capacity + 1)
    for w in range(weight, capacity + 1):
        dp[w] = value

    for child in children[i]:
        child_dp = dfs(child)
        for j in range(capacity, weight - 1, -1):
            for k in range(j - weight + 1):
                dp[j] = max(dp[j], dp[j - k] + child_dp[k])
    return dp

状压DP

数位DP

DP优化

经典问题

• 鸡蛋掉落
  f(k, n)表示有k个鸡蛋、n层楼时，最坏情况下的最小尝试次数。

def superEggDrop(self, k: int, n: int) -> int:

        cache = dict()

        def dp(k, n):
            if n == 0:
                return 0
            if k == 1:
                return n

            item = (k, n)
            if item in cache:
                return cache[item]

            left = 1
            right = n
            while left + 1 < right:
                mid = (left + right) // 2
                broken = dp(k - 1, mid - 1)
                not_broken = dp(k, n - mid)
                if broken == not_broken:
                    left = mid
                    right = mid
                else:
                    if broken > not_broken:
                        right = mid
                    else:
                        left = mid

            res = n
            for x in range(left, right + 1):
                res = min(res, 1 + max(dp(k - 1, x - 1), dp(k, n - x)))
            cache[item] = res
            return res

        return dp(k, n)