X

LEETCODE 1269. Number of Ways to Stay in the Same Place After Some Steps 解题思路分析

题目大意:

停在原地的方案数

有一个长度为 arrLen 的数组,开始有一个指针在索引 0 处。

每一步操作中,你可以将指针向左或向右移动 1 步,或者停在原地(指针不能被移动到数组范围外)。

给你两个整数 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 处。
向右,向左
不动,不动

示例 3:

输入:steps = 4, arrLen = 2
输出:8

提示:

  • 1 <= steps <= 500
  • 1 <= arrLen <= 10^6

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1269

解题思路分析:

这又是一道标准的DP题目,之前博客多次提到过,理论上动态规划题目都可以使用递归加记忆数组来代替。本人更热衷于递归,因此本题使用递归来解题。

对于当前点可移动的方案有以下三种情况:

  1. 若当前位置大于0,可以向左移动
  2. 若当前位置小于最后一位,可以向右移动
  3. 任何位置都可以原地不动

递归终止条件为当前index为0,并且剩余步数为0,此时步数方案加一。

还有一个终止条件是,当步数小于index时,由于所剩的步数无法支持返回起点,此时不存在返回起点的步数方案,返回0。这一点也可以得出另一个结论,不论数组长度为多长,要想最终返回起点,我们要保证足够的往返步数,因此,能够到达的最远index一定不能超过步数的一半。

我们可以定义一个memo记忆数组,int[][] memo,memo[i][j]代表,还剩下i步时,从下标j返回下标0的方案数。最终答案为memo[steps][0]。

实现代码:

int[][] memo; // 记忆数组
public int numWays(int steps, int arrLen) {
    // 初始化记忆数组
    // memo[i][j]代表,还剩下i步时,从下标j返回下标0的方案数
    // 由于能够到达的最远index一定不能超过步数的一半,
    // j的最大值为steps/2+1
    memo=new int[steps+1][steps/2+1];
    // 递归求解
    return helper(steps, arrLen, 0);
}

int helper(int steps, int arrLen, int index){
    // 如果剩余步数小于index,说明已无法返回起点,返回0
    if(steps<index) return 0;
    // 如果返回起点时刚好使用完步数,方案加一。
    if(steps==0 && index==0) return 1;
    // 如果记忆数组存在当前解,直接返回。
    if(memo[steps][index]>0) return memo[steps][index];
    long res=0; // 返回结果
    // 当index大于0时,可以向左移动
    if(index>0){
        res=(res+helper(steps-1,arrLen,index-1))%1000000007;
    }
    // 当index小于数组末尾时,可以向右移动
    if(index<arrLen-1){
        res=(res+helper(steps-1,arrLen,index+1))%1000000007;
    }
    // 任何位置都可以原地不动
    res=(res+helper(steps-1,arrLen,index))%1000000007;
    // 结果存入记忆数组
    memo[steps][index]=(int)res;
    return (int)res;
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 100.00% of Java online submissions forNumber of Ways to Stay in the Same Place After Some Steps.

Memory Usage: 35.5 MB, less than 100.00% of Java online submissions for Number of Ways to Stay in the Same Place After Some Steps.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1269-number-of-ways-to-stay-in-the-same-place-after-some-steps-解题思路分析/
Categories: leetcode
kwantong: