LeetCode50天刷题计划（Day 39 —恰好移动 k 步到达某一位置的方法数目（8.00-8.50）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

第一题是昨天mhy周赛的第二题，记忆化dfs

一、题目

恰好移动 k 步到达某一位置的方法数目

给你两个 正 整数 startPos 和 endPos 。最初，你站在 无限 数轴上位置 startPos 处。在一步移动中，你可以向左或者向右移动一个位置。

给你一个正整数 k ，返回从 startPos 出发、恰好 移动 k 步并到达 endPos 的 不同 方法数目。由于答案可能会很大，返回对 109 + 7 取余 的结果。

如果所执行移动的顺序不完全相同，则认为两种方法不同。

注意：数轴包含负整数。

示例

示例 1：
输入：startPos = 1, endPos = 2, k = 3
输出：3
解释：存在 3 种从 1 到 2 且恰好移动 3 步的方法：

• 1 -> 2 -> 3 -> 2.
• 1 -> 2 -> 1 -> 2.
• 1 -> 0 -> 1 -> 2.
  可以证明不存在其他方法，所以返回 3 。

示例 2：
输入：startPos = 2, endPos = 5, k = 10
输出：0
解释：不存在从 2 到 5 且恰好移动 10 步的方法。

提示

1 <= startPos, endPos, k <= 1000

二、思路

一开始的思路是dfs，但是超时。用记忆化搜索就不会超时：

记忆化搜索和递归、动态规划

①记忆化搜索是剪枝的递归,但是递归深度依然很大,需要很大的调用栈,存储很多参数,内存占用较大。
动态规划只是调用一次,递归深度为1. 动态规划用数组去存,记忆化搜索利用的是哈希表。从理解上,记忆化搜索易于理解。
1）举个例子：斐波那契数列
普通递归：O（2^n）

int f(int n) {
	if (n <= 1) return 1;
	return f(n - 1) + f(n - 2);
}
1
2
3
4

记忆化搜索：O（n）: 在搜索的过程中，把计算过的值用数组或STL容器存储下来，减少重复搜索的时间；这样遇到这个数就可以直接返回其值了

 dp[100010] = {0};
 f(ll n) {
	if (n <= 1) return dp[n] = 1; //赋值后将这个值返回
	if (dp[n]) return dp[n]; // 若记忆数组中有值，就把它返回
	return dp[n] = f(n - 1) + f(n - 2);
}
1
2
3
4
5
6

②记忆化搜索是动态规划的优化。因为动态规划往往要遍历所有的状态，而搜索可以排除一些无效状态，更重要的是搜索还可以剪枝（比如0-1背包问题减去了大量的无用搜索），因此在时间和空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。

dfs与记忆化dfs

在本题中，在dfs的过程中形成结果，每次递归对结果函数数组进行更改，这种选择是不明智的。因为其实返回结果只是一个数字，且可以被划分为更小的子问题，比如：f（x）=(f(x - 1, left - 1) + f(x + 1, left - 1)) % MOD
因此采用记忆化递归，作传入参数的哈希值，记录每次对应的返回值，这个用@cache实现，其实本质上也相当于用dp数组记录函数值（上文的斐波那契数列），只是此时的参数不止一个，无法自己建立一维数组。
这样一来，以后再次遇到这个状态的时候，就不必重新求解了。

三、代码

1.超时

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        edge=pow(10,9)+7 #边界
        count=[0]
        def dfs(index,step,count): #步长
            if(step == k): #终止条件，步数走完
                if(index == endPos): #走到终点了
                    count[0]+=1
                    if(count[0] == edge): #边界
                        count[0]=0
                return #没到终点也得
            if(abs(endPos-index)>k-step): #剪枝
                return
            dfs(index+1,step+1,count) #往右走
            dfs(index-1,step+1,count) #往左走
        dfs(startPos,0,count)
        return count[0] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.ac

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        #记忆化dfs
        @cache #python里记忆化的装饰器，类似于lrucache，记录已有的结果，方便之后调用（应该是将一个函数的参数形成hash值，然后下次再计算与此函数）
        def dfs(pos,cur):
            if pos == endPos and cur == 0: #正好走到终点
                return 1
            if cur == 0: #走完了没到终点
                return 0
            return dfs(pos + 1,cur - 1) + dfs(pos -1 ,cur-1) #
        #返回（调用）
        return dfs(startPos,k) % int(1e9 + 7)
1
2
3
4
5
6
7
8
9
10
11
12