动态规划canConstruct问题：为何空字符串作为递归基例返回true？

首先得澄清一个关键：Alvin的表述大概率是口误，正确的逻辑应该是生成空字符串不需要选取任何数组元素，这才是这个基例成立的核心原因。

为什么这个基例合理？我们回到问题本身：canConstruct(target, wordBank)的语义是「是否能通过拼接wordBank中的元素（可重复使用、顺序任意）得到target字符串」。当target是空字符串时，我们什么都不用做就已经满足条件了——毕竟空字符串本身就是我们要的结果，不需要从数组里选任何元素，这种情况天然成立，所以返回true。

结合你提到的示例来看递归过程：

• 初始调用canConstruct('StakeBoard', ['sta', 'te', 'bo', 'ard'])，匹配到前缀'sta'，递归调用canConstruct('keBoard', [...])
• 接着匹配'te'，递归调用canConstruct('Board', [...])
• 匹配'bo'，递归调用canConstruct('ard', [...])
• 匹配'ard'，递归调用canConstruct('', [...])
• 触发基例返回true，于是整个递归链层层向上返回true，最终得到正确结果

如果把这个基例设为false会怎么样？那当我们把目标字符串完全拆解为空的时候，会错误地判定为“无法构造”，这显然和实际逻辑矛盾——毕竟我们已经通过一步步拆解完成了构造，空字符串就是拆解到最后的终点，理应返回成功。

简单来说，这个基例是递归终止的“成功终点”，对应「已经完全构造出目标字符串」的状态，是符合问题逻辑的合理设定。

内容的提问来源于stack exchange，提问作者Frederick Scott Smith