GuilinDev

Lc1269

05 August 2008

1269. Number of Ways to Stay in the Same Place After Some Steps

在大小为 arrLen 的数组中的索引 0 处有一个指针。在每一步，可以在数组中向左移动 1 个位置，向右移动 1 个位置，或者留在原地（指针在任何时候都不应该放在数组之外）。

给定两个整数 step 和 arrLen，返回在精确 step 之后指针仍位于索引 0 的方式数。由于答案可能太大，因此以 109 + 7 为模返回。

Top Down DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    int MOD = 1000000007;
    int[][] dp;
    public int numWays(int steps, int arrLen) {
        dp = new int[steps+2][steps+1];
        for(int[] arr : dp)
        {
            Arrays.fill(arr, -1);
        }
        dp[0][0] = 1;
        return dfs(0, steps, arrLen);
    }
    
    public int dfs(int pos, int steps, int arrlen)
    {
        if(pos > steps)return 0;
        if(dp[pos][steps]!=-1)return dp[pos][steps];
        
        int res = 0;
        res+=dfs(pos, steps-1, arrlen);
        res%=MOD;
        if(pos+1<arrlen)
        {
            res+=dfs(pos+1, steps-1, arrlen);
            res%=MOD;
        }
        
        if(pos-1>=0)
        {
            res+=dfs(pos-1, steps-1, arrlen);
            res%=MOD;
        }
        
        dp[pos][steps] = res;
        return res;
    }
}

Bottom Up

Initialize:

  • bound = min(arrLen , steps/2+1)
  • that’s how many positions the algo will consider at most

dpPrev[bound], dpNext[bound]

dpPrev[i] is a number of ways to reach position i calculated for the prev step

dpNext[i] is the same for the next step

Initially, dpPrev[0] = 1

Then repeat steps times:

calculate dpNext from dpPrev

dpNext[i] = (dpPrev[i] + dpPrev[i-1] + dpPrev[i+1]) % MOD

(when index is out of bounds, fall back to 0)

swap dpPrev and dpNext

Once done, return dpPrev[0]

TC: O(steps * min(arrLen, steps))

SC: O(min(arrLen, steps))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    private static final long MOD = 1_000_000_007;

    public int numWays(int steps, int arrLen) {
        int bound = Math.min(arrLen, steps / 2 + 1);
        long[] dpPrev = new long[bound];
        dpPrev[0] = 1;
        long[] dpNext = new long[bound];

        for (int step = 0; step < steps; step++) {
            for (int i = 0; i < bound; i++) {
                dpNext[i] = dpPrev[i];
                if (i > 0)
                    dpNext[i] += dpPrev[i - 1];
                if (i < bound - 1)
                    dpNext[i] += dpPrev[i + 1];
                dpNext[i] %= MOD;
            }

            long[] tmp = dpPrev;
            dpPrev = dpNext;
            dpNext = tmp;
        }

        return (int) dpPrev[0];
    }
}
This site is open source. Improve this page.