有一个问题一直困扰着我,就是使用备忘录进行记忆化搜索的方式到底算不算动态规划?有此疑惑是因为我常常发现,在 LeetCode 上使用记忆化搜索求解往往效率很差,时间复杂度排在后 20%,而使用 DP table 进行递推的效率则好很多;以及看到很多题解中将动态规划与记忆化搜索(备忘录)并列介绍。