Python使用动态规划(DP)优化N维棋盘生成速度未提升问题

问题核心原因 #

你的动态规划（记忆化）方案从设计到逻辑都存在问题，所以完全起不到提速效果，甚至本身还有功能bug：

• 记忆化key的设计完全错误，没有可命中的重复计算场景
  你当前memo的key是len(dimensions)也就是维度的层数，完全没有记录每层的具体尺寸。更关键的是：在一次生成N维棋盘的调用过程中，每个层数只会被调用1次，比如生成6维棋盘时，层数为6、5、4、3、2、1的分支各只会执行一次，你的缓存根本没有任何重复命中的机会，反而多了字典读写的额外开销，自然和朴素递归速度没有差异。
  就算你把key改成整个dimensions元组，对于单次生成调用来说，同样不会有重复的参数触发缓存命中，还是不会提速。
• 记忆化逻辑本身有功能bug
  你直接把生成的列表引用存在缓存中返回，会导致最终生成的棋盘所有同层级子数组指向同一个内存对象：比如你修改arr[0][0][0] = 9，会发现所有arr[x][y][0]的值都变成了9，完全不符合棋盘每个格子独立的要求，逻辑本身就是错的。
• 该场景本身没有可优化的冗余计算
  生成所有元素独立的N维棋盘，本质上就需要初始化「所有维度乘积」数量的节点，时间复杂度固定为O(Πdimensions)，不存在可以剪枝、复用的冗余计算，强行加记忆化本来就不会有提速效果。

正确提速方案 #

如果要大幅提升生成速度，不要用Python原生递归的列表生成式，直接用数值计算库numpy实现：

import numpy as np
def createboard_nd_fast(dimensions, value=None):
    return np.full(dimensions, value).tolist()

同等参数下比你原来的递归版本快数十倍以上，且逻辑正确。

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