二维数组指定索引值计算方案优化：从O(m*n)到更优解法

问题描述：给定二维数组，第一行和第一列所有位置值为1，其余位置的值等于其上方与左侧值之和（即 (row, col) = (row-1, col) + (row, col-1)），需实现函数接收索引对(row, col)返回对应数值。现有带记忆化的动态规划解法（时间O(mn)、空间O(mn)），寻求优化方案。

现有解法分析 #

你提供的代码用lru_cache实现了自顶向下的记忆化递归，本质是动态规划的一种形式。它的问题在于：

• 空间复杂度O(mn)，缓存了所有中间状态，大维度输入下会占用过多内存；
• 递归调用存在栈溢出风险（比如m/n达到1e4级别时）；
• 时间效率仍有优化空间。

优化方案 #

1. 空间优化的动态规划（O(min(m,n)) 空间）

思路：计算当前行仅依赖上一行的数据，因此可以用一维数组滚动更新，将空间复杂度压缩到O(min(m,n))。

def solution(m: int, n: int):
    # 优先处理较小维度，减少数组长度
    if m < n:
        m, n = n, m
    # dp数组初始对应第一行（全1）
    dp = [1] * (n + 1)
    # 逐行更新
    for _ in range(1, m + 1):
        for j in range(1, n + 1):
            # dp[j] = 上方值（原dp[j]） + 左侧值（已更新的dp[j-1]）
            dp[j] += dp[j - 1]
    return dp[n]

该方案时间复杂度仍为O(mn)，但彻底避免了递归栈溢出，空间占用大幅降低。

2. 数学公式法（O(1) 空间，O(min(m,n)) 时间）

思路：这个问题本质等价于从(0,0)走到(m,n)的路径数（仅允许向右/向下移动），对应组合数公式：
$$C(m+n, m) = C(m+n, n) = \frac{(m+n)!}{m! \cdot n!}$$
通过递推计算组合数，避免直接计算大阶乘，效率最优。

def solution(m: int, n: int):
    # 取较小值减少循环次数
    k = min(m, n)
    result = 1
    for i in range(1, k + 1):
        # 递推公式：C(m+n, i) = C(m+n, i-1) * (m+n -i +1) // i
        result = result * (m + n - i + 1) // i
    return result

示例验证：输入(5,3)时，计算C(8,3)=56，与题目示例一致。该方案适用于所有规模的输入，是最优解。

3. 递归栈优化（可选）

若坚持递归思路，可改为迭代式自底向上DP，但空间优化的DP方案已经覆盖了这种场景，无需额外实现。

方案对比 #

内容的提问来源于stack exchange，提问作者saahil sanganeria