[记忆化dfs]leetcode2400：恰好移动 k 步到达某一位置的方法数目(medium)

题目：

---

题解：

思路：记忆化 dfs

• 状态定义参考 1575. 统计所有可行路径，本题为该题的简化版本，状态转移的计算量只有 2 个。
• 状态f[pos][rest]=c：表示在当前位置 pos 上，还能走 rest 步，走到终点 end 的总路径步数为 c 条。
• 状态转移：向前走一步或者向后走一步，这两种情况进行枚举即可。

---

代码如下：

const int mod = 1e9+7, N = 1010;
using PII = pair<int,int>;
class Solution {
public:
    // 记忆化 dfs
    // 时间复杂度为 O(n*k*2)，状态的数量为 O(n*k)，对于每个状态的转移需要 O(2)的时间复杂度
    // 空间复杂度为 O(n*k)，为状态的数量
    // f[pos][rest]=c 表示在当前位置 pos 上，还能走 rest 步，走到终点 end 的总路径步数为 c 条。
    map<PII,int> f;
    int numberOfWays(int pos, int end, int rest) {
        // 无法直接从位置 pos 到达终点 end，那么间接也是无法从位置 pos 走到终点 end 的，所以直接返回 0
        if(abs(pos-end)>rest)return 0;
        // 由于 abs(pos-end)>=0，因此 abs(pos-end)>=rest>=0
        if(rest==0)return pos==end;
        // 当前的状态
        PII cur={pos,rest};
        // 当前状态已经被计算过了，直接返回计算过的状态值
        if(f.count(cur))return f[cur];
        // 进行状态转移：枚举两种转移方式，向前走一步或者向后走一步
        return f[cur]=(numberOfWays(pos-1,end,rest-1)+numberOfWays(pos+1,end,rest-1))%mod;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22