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

题目

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];

    }

}

【力扣】2400. 恰好移动 k 步到达某一位置的方法数目的相关教程结束。