掷骰子目标和问题递归解法的时间空间复杂度分析及疑问

问题背景 #

给定n个k面骰子（面数为1到k），求掷出的点数和等于target的方法数，结果需对10^9+7取模。以下是你给出的递归解法：

def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        modulo = 10**9 + 7
        def permutations(dice, k, target):
            if dice == 0:
                return 1 if target == 0 else 0
            num_ways = 0
            for i in range(1, k+1):
                num_ways += permutations(dice-1, k, target-i)
            return num_ways
                
        return permutations(n, k, target) % modulo

关于target是否纳入复杂度分析 #

你给出的纯递归解法时间复杂度为O(k^n)是准确的，不需要将target（t）纳入复杂度分析。原因是：递归树的每一层对应一个骰子，每个节点都会展开k个子节点，只要target处于合法范围（n ≤ t ≤ n*k），递归会完整遍历所有可能的骰子组合路径；即使target不在合法范围，递归会直接返回0，但这种边界情况不影响最坏时间复杂度的评估，因此通常用O(k^n)描述该解法的时间复杂度。空间复杂度O(n)来自递归栈的深度，同样与target无关。

记忆化解法的复杂度逻辑确认 #

记忆化解法通过缓存(剩余骰子数, 剩余目标和)的状态结果，避免重复计算，其复杂度分析逻辑如下：

• 时间复杂度O(ntk)：
  1. 总状态数：剩余骰子数有n+1种可能（0到n），每个骰子数对应的剩余目标和最多有t+1种可能（0到t），有效状态数为O(n*t)。
  2. 每个状态的计算：对于每个(dice, rem)状态，需要遍历k个可能的骰子面（1到k），每个遍历对应一个子状态(dice-1, rem-i)，因此每个状态的计算时间为O(k)。
  3. 总时间为状态数乘以单个状态的计算时间，即O(ntk)。
• 空间复杂度O(n*t)：
  主要来自记忆化缓存的存储空间，用于存储所有O(nt)个状态的计算结果；递归栈的空间最多为O(n)，远小于缓存空间，因此整体空间复杂度为O(nt)。

内容的提问来源于stack exchange，提问作者Victor Cui