解决动态规划的基本步骤，分别是：设置状态、枚举子问题，更新答案。
其实，这每一步都不是那么好做到的，需要有足够的经验和相关数学知识来得出并化简动态转移方程，这对入门选手是很不友好的。
今天，我来介绍一种秒解DP的方法，适合入门选手快速熟悉动态规划问题，并逐步积累经验。
他就是——
搜索！
搜索！
搜索！
你可能会好奇：动态规划思想不就是要解决搜索算法时间复杂度过高的问题吗？这里怎么反而用搜索来解决动态规划问题了呢？
当然，这里的搜索并不是普通的搜索，而是记忆化搜索。
我们还是用01背包问题为例子，来讲解一下记忆化搜索的原理和实现方法。
搜索程序显然是很容易就能写出来的，核心代码如下：
这段代码中，step表示当前处理到那个物品，v表示背包已用的容量，sum表示当前背包内物品总共的价值。搜索过程分当前物品选或不选进行递归。
这代代码的时间复杂度是O(2^N)，显然很难接受。
这时候，我们可以换一个搜索思路，把尾递归换成首递归。
参考一下代码：
这段代码也是很好理解的，step表示当前处理的物品，v表示当前背包剩下的容量。
但是，这么修改后时间复杂度也是O(2^N)的，并没有优化，怎么办呢？
我们观察代码，发现每层循环的自变量是step和v，因变量是返回值tmp。很显然，一旦step和v确定了，返回值tmp也就确定了。
这么说来，我们是不是开一个二维数组把tmp的值存下来，就只需要计算一次就好了，省事。
核心代码如下：
注意，f数组的初值为-1。
那么，这么处理后，代码的时间复杂度还是O(2^N)吗？
我们发现，如果f[step][v]不是-1（也就是已经得出了应该的返回值是），就会直接返回，不会再继续递归。那么，最坏情况下就是把f数组的每个值都算出来罢了。时间复杂度为O(NV)，和用for循环实现的时间复杂度是一样的，但由于搜索需要递归压栈，可能常数会大一点。
记忆化搜索解决动态规划问题是很容易理解的。我们只需要按照写搜索的方法先写一个程序，然后找到自变量（其实就是递归参数）和因变量（每一层递归的返回值），就能快速实现记忆化搜索的程序。
【信息学竞赛从入门到巅峰】，一个专注于分享OI/ACM常用算法及知识的公众号。
