摘要记忆化检索是典型的改变空间时间的思想。
存储检索的典型应用场景可能经过不同路径转移到相同状态的dfs问题。
更具体而言，如果需要以具有分层结构的图(不是树，即当前层中的不同节点可能转移到下一层中的相同节点)自上而下地进行dfs搜索，则存储搜索技术可能会导致
例：青蛙过河的主题表明青蛙要过河。 假设河流被分成几个单元，每个单元中可能都有碎石。 青蛙可以跳上石头，但不能跳进水里。
请列出石头位置列表stones (按单元格编号的升序显示)，判断青蛙是否能过河，也就是说，在最后一步能否跳到最后一块石头。
最初，假设青蛙默认站在第一块石头上，第一步只能跳一个单位。 也就是说，只能从单元格1跳到单元格2。
如果青蛙在前一步中跳了k个单位，则只能选择k - 1、k或k 1个单位的下一跳距离。 也请注意，青蛙只能向前(终点的方向)跳跃。
例1输入： stones=[0、1、3、5、6、8、12、17]输出： true说明：青蛙可以过河。 跳如下。 从1跳至第2石，从2跳至第3石，从2跳至第4石，从3跳至第6石范例2输入： stones=[0、1、2、3、4、8、9、11]输出： 对于我构建的示例stones=[0、1、3、4、5、6、7、10、15]，搜索路径如下：
从状态[ 5，1 ]和状态[ 5，2 ]中选择状态[ 7，2 ]，而[7,2]这个状态并不能转移到终点这个结论是可以被存储起来的，避免对同一个结论的重复计算。
就像很多人走在迷宫里一样，前人去了[ 7，2 ]，意识到没有出去的路(无法过渡到目标状态)，当他回到这个节点时，在这里立一个留言板[记忆化标签]，告诉他不要来这个地方，不要走前人种树乘凉后人。
代码/*详细信息： dfs的参数pos是数组中的下标，而不是位置。 这样就更容易记录到vector中。 */class解决方案{ public : vector unordered _ map int，bool flag； BOOLDFS(intpos，int preJump，vectorint stones ) ) if ) pos==stones.size(-1 ) return true； if(flag[pos].count(prejump ) ) {返回假； }for(intjump=prejump-1； 跳跃=prejump1； jump ) {if(jump=0) continue； intnextpos=lower _ bound (stones.begin )、stones.end )、stones[pos] jump )- stones.begin )； 下一个销售点！=stones.size (stones [ nextpos ]==stones [ pos ] jump DFS ) next pos，jump，stones ) { return true； }返回标志[ pos ] [ pre jump ]=false； }boolcancross(vectorintstones ) { int n=stones.size )； flag.resize(n； 返回DFS (0，0，stones )； }； 学习算法初期最需要锻炼的是对症治疗的能力。 让我们来看看典型的无法使用记忆化搜索的反例：
反例：停留在原地的计划数的主题表示有一个名为arrLen的长度数组，在索引0处有指针。
在每个步骤的操作中，可以将指针向左或向右移动一步，也可以将其停止在原地(指针不能移动到数组之外)。
给你两个整数steps和arrLen。 请计算后返回。 在正好执行steps次操作后，指针仍指向索引为0的方案数。
因为答案可能会变大，所以计划数模10^
9 + 7 后的结果。 示例1 输入：steps = 3, arrLen = 2输出：4解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。向右，向左，不动不动，向右，向左向右，不动，向左不动，不动，不动 示例2 输入：steps = 2, arrLen = 4输出：2解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。向右，向左不动，不动 分析如图所示，图中每个节点S值表示当前还剩多少步要走，pos值表示当前处在的位置。每个节点对应一个方案数，我们要计算的是根节点(S=3,pos=0)的方案数。
乍一看本题也是自上而下在有层次结构的图中搜索，且也符合当前层的不同节点都转移到下一层的同一节点。但问题在于本题并不是dfs过程，因为要想知道(S=2,pos=1)节点的值，需要同时知道(S=1,pos=0)、(S=1,pos=1)、(S=1,pos=2)这三个节点的值。其实对于计算方案数的问题，最先想到的方法应该是动态规划。事实证明这道题的确用动态规划是最好的解法。
动态规划之所以能比递归快很多，就是通过将重复子问题的解存储起来，重复子问题的解只需算一次即可，不必重复计算，自底向上一步步得到原问题的解。从这个角度来说，动态规划和记忆化搜索的共同点在于都是空间换时间的思想。
回到本题的dp解法：
dp定义：dp[i][j] 表示还可以走i步时，位于位置j的方案数初始化：dp[0][0] = 1待求结果：dp[steps][0]状态转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j+1] 代码 class Solution {public: int numWays(int steps, int arrLen) { // dp[i][j] 表示还剩i个step时位于位置j的方案数。要求dp[steps][0] // 由于steps步后，位置最远走到steps,因此列数应该是min(steps+1,arrLen) int col = min(steps+1, arrLen); vector<vector<int>> dp(steps+1,vector<int>(col, 0)); // init dp[0][0] = 1; int mod = 1000000000+7; for(int i=1;i<=steps;i++) { for(int j=0;j<col;j++) { dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod; if(j-1>=0) dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod; if(j+1<col) dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % mod; if(i==steps && j==0) break; } } return dp[steps][0]; }};滚动数组优化：
class Solution {public: int numWays(int steps, int arrLen) { // 由于steps步后位置最远走到steps,因此列数可以优化为min(steps+1,arrLen)。可以大大降低空间和时间复杂度 // 由于转移到dp[i]只需要dp[i-1]，因此使用滚动数组，可以将dp数组的行数优化为2。 int col = min(steps+1, arrLen); vector<vector<int>> dp(2,vector<int>(col, 0)); // init dp[0][0] = 1; int mod = 1000000000+7; for(int i=1;i<=steps;i++) { for(int j=0;j<col;j++) { int dst = i%2, src = 1 - i%2 ; // i为奇数时从[0]转移到[1]，反之亦然 dp[dst][j] = 0; // 不要忘记将待填充的dp初值设为0，因为里面保存这之前的数据 dp[dst][j] = (dp[dst][j] + dp[src][j]) % mod; if(j-1>=0) dp[dst][j] = (dp[dst][j] + dp[src][j-1]) % mod; if(j+1<col) dp[dst][j] = (dp[dst][j] + dp[src][j+1]) % mod; if(i==steps && j==0) break; } } if(steps % 2) return dp[1][0]; return dp[0][0]; }};