Register_int @ 2022-07-30 15:07:07
rt，记忆化搜索的数位 dp 时间复杂度是什么？
by TernaryTree @ 2022-07-30 15:08:45
我觉得是取决于 dp 数组的总大小。
by Rubidium_Chloride @ 2022-07-30 15:10:01
转移复杂度 * 数组大小吧。
by Register_int @ 2022-07-30 15:10:21
@ternary_tree 您好，lim和lead
by BreakPlus @ 2022-07-30 15:12:12
@Register_int 那个是常数级别的影响啊
by fjy666 @ 2022-07-30 15:12:41
@Register_int 当有 lead 时，要么转移一层到没有 lead，要么开头为0还有lead（只有一种情况），所以时间复杂度不变，lim同理
by BreakPlus @ 2022-07-30 15:12:53
你发现 lim 为 0 的情况数是线性的
by fjy666 @ 2022-07-30 15:13:20
简单来说 dfs 有 lead/lim 的形成一条链
by Register_int @ 2022-07-30 15:39:43
@fjy666 谢