大家好,又见面了,我是你们的朋友全栈君。
概述
记忆化搜索是一种典型的空间换时间的思想。
记忆化搜索的典型应用场景是可能经过不同路径转移到相同状态的dfs问题。...分析
对于我构造的示例 stones = [0,1,3,4,5,6,7,10,15],搜索路径如下:
可以看到从状态[5,1]和状态[5,2]都能转移到状态[7,2],而[7,2]这个状态并不能转移到终点这个结论是可以被存储起来的...(转移到没有打上记忆化标签的状态)。...乍一看本题也是自上而下在有层次结构的图中搜索,且也符合当前层的不同节点都转移到下一层的同一节点。...可以大大降低空间和时间复杂度
// 由于转移到dp[i]只需要dp[i-1],因此使用滚动数组,可以将dp数组的行数优化为2。