冲刺阶段：算法优化技巧——记忆化搜索与迭代DP转换实战

在蓝桥杯等算法竞赛中，算法的优化是提高解题效率的关键。本文将重点探讨记忆化搜索与迭代动态规划（DP）的转换技巧，并通过斐波那契数列和背包问题的实例，演示这一转换过程，解析空间换时间的策略。

一、记忆化搜索与迭代DP简介

记忆化搜索是一种自顶向下的优化技术，通过存储已解决子问题的结果来避免重复计算。迭代DP则是自底向上的方法，通过从小规模问题逐步构建到大规模问题的解。

二、记忆化搜索与迭代DP的转换

在某些情况下，记忆化搜索可以转换为迭代DP，以进一步优化空间和时间复杂度。转换的关键在于识别子问题的依赖关系，并构建相应的状态转移方程。

1. 斐波那契数列

斐波那契数列是一个经典的递归问题，定义为：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) （n ≥ 2）

记忆化搜索实现：

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

迭代DP实现：

def fib_iter(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]

通过迭代DP，我们将空间复杂度从O(n)降低到O(1)，只需存储前两个状态：

def fib_iter_optimized(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

2. 背包问题

背包问题是经典的优化问题，定义如下：

给定n个物品，每个物品有重量和价值。
背包容量为W，求能装入背包的最大价值。

记忆化搜索实现：

def knapsack_memo(weights, values, W, n, memo={}):
    if (n, W) in memo:
        return memo[(n, W)]
    if n == 0 or W == 0:
        return 0
    if weights[n-1] > W:
        result = knapsack_memo(weights, values, W, n-1, memo)
    else:
        result = max(values[n-1] + knapsack_memo(weights, values, W - weights[n-1], n-1, memo),
                     knapsack_memo(weights, values, W, n-1, memo))
    memo[(n, W)] = result
    return result

迭代DP实现：

def knapsack_iter(weights, values, W, n):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

通过空间优化，可以将二维DP数组优化为一维数组：

def knapsack_iter_optimized(weights, values, W, n):
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
    return dp[W]