题目

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

解题思路

观察上面示例，容易画出下面的递归树，因此可以考虑DFS。

DFS

很容易写出DFS的代码

class Solution {
    int res = 0;  //记录可行路径数

    public int numberOfWays(int startPos, int endPos, int k) {
        dfs(startPos, endPos, k);
        return res;
    }

    void dfs(int startPos, int endPos, int k){
    	// 递归边界，走了k步
        if(k == 0){
        	// 走到终点了，答案加一
            if(startPos == endPos){
                res++;
            }
            return;
        }
        // 向左走
        dfs(startPos - 1, endPos, k - 1);
        // 向右走
        dfs(startPos + 1, endPos, k - 1);
    }
}

记忆化搜索

上述代码可以解决示例1，对于规模大一点的例子就超时，说明思路是对的，接下来就是优化了，自然的想法就是加个备忘录，那就要考虑是否存在重叠子问题。

对于示例1，下图展示了存在的重叠子问题。

在上图中，当前的坐标和剩余 k 步就是问题的状态，因此加一个二维数组备忘录 memo。

注意：由于坐标可能是负值，所以可以用 startPos + 偏移 来防止数组索引为负值。

class Solution {
	// 备忘录
    int[][] memo;
    // 取余
    int MOD = 1000000000 + 7;

    public int numberOfWays(int startPos, int endPos, int k) {
    	// 初始化备忘录
        memo = new int[6000 + 10][6000 + 10];
        for(int[] arr : memo){
            Arrays.fill(arr, -1);
        }
        return dfs(startPos, endPos, k);
    }

    int dfs(int startPos, int endPos, int k){
    	// 已经计算过该子问题，则直接返回
        if(memo[startPos + 3000][k] != -1){
            return memo[startPos + 3000][k];
        }
        // 走完 k 步
        if(k == 0){
            if(startPos == endPos){  // 走到终点了，是一种方法
                memo[startPos + 3000][k] = 1;
            }else{  // 没有走到终点，方案数为0
                memo[startPos + 3000][k] = 0;
            }
            return memo[startPos + 3000][k];
        }
        // 记录往左走和往右走的方案总数
        int res = 0;
        // 加上往左走的方案数
        res += dfs(startPos - 1, endPos, k - 1);
        // 加上往右走的方案数
        res += dfs(startPos + 1, endPos, k - 1);
        // 结果求余
        memo[startPos + 3000][k] = res % MOD;
        return memo[startPos + 3000][k];
    }
}