題目

ou have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay
Example 2:

Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay
Example 3:

Input: steps = 4, arrLen = 2
Output: 8

Constraints:

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

有一個長度為 arrLen 的數(shù)組，其實(shí)位置為 0 ，每次可以向右一步、向左一步、留在原地，經(jīng)過 steps 次操作后，仍處于位置 0 ，一共有多少種路徑可以滿足要求。
由于結(jié)果可能非常大，可以用 10^9 + 7 取模。
約束條件：
1 <= steps <= 500
1 <= arrLen <= 10^6

解題思路

1. 如要第 n 步在位置 0， 則第 n-1 步應(yīng)該位于位置 0 或者位置 1
2. 若要第 n-1 步在位置 0 ，則第 n-2 步應(yīng)該位于位置 0 或者位置 1
3. 若要第 n-1 步在位置 1 ，則第 n-2 步應(yīng)該位于位置 0 、位置 1 或者位置 2
4. 。。。

這是動態(tài)規(guī)劃問題，正向解析就是

1. 一步到達(dá)位置 0 和位置 1 的路徑數(shù)量為 1，arr1[0]=1，arr1[1]=1，
2. 兩步可到達(dá)的位置最遠(yuǎn)為位置 2 或者數(shù)組長度 arrLen<2 ，并且可以由一步到達(dá)的路徑數(shù)量加的，arr2[0]=arr1[0]+arr1[1]，arr2[1]=arr1[0]+arr1[1]+arr1[2]，arr2[2]=arr1[1]+arr1[2]+arr1[3]，arr2[arrLen-1]=arr1[arrLen-2]+ar1r[arrLen-1]
3. 三步可到達(dá)的位置最遠(yuǎn)為位置3 或者數(shù)組長度 arrLen<3 ，并且可以由兩步到達(dá)的路徑數(shù)量加的，arr3[0]=arr2[0]+arr2[1]，arr3[1]=arr2[0]+arr2[1]+arr2[2]，...，arr3[arrLen-1]=arr2[arrLen-2]+arr2[arrLen-1]

代碼實(shí)現(xiàn)

func numWays(_ steps: Int, _ arrLen: Int) -> Int {
        //若步數(shù)或者長度為1時，則只有一種路徑
        if arrLen <= 1 || steps <= 1{
            return 1
        }
        //設(shè)置模
        let mod = 1000000007
        //初始化一步到達(dá)的路徑數(shù)量數(shù)組，可達(dá)最遠(yuǎn)位置1，長度為1+1=2，但由于計算二步到達(dá)路徑數(shù)量數(shù)組時，會用到一步到達(dá)位置2的路徑數(shù)量，所以需要額外加一個元素，即長度為2+1=3
        var arr = [1, 1, 0]
        //循環(huán)從二步到steps步
        for i in 2 ... steps {
            //可到達(dá)的最遠(yuǎn)位置為步數(shù)與數(shù)組長度的較小值
            let max = min(arrLen-1, i)
            //初始化臨時i步到達(dá)的路徑數(shù)量數(shù)組，長度為(max+1)+1=max+2
            var temp = [Int](repeating: 0, count: max+2)
            //循環(huán)i步可到達(dá)位置 0 ~ max 的路徑數(shù)量數(shù)組
            for j in 0 ... max{
                //先獲取 i-1 步到達(dá)位置 j 的路徑數(shù)量
                var ans = arr[j]
                switch j {
                //若位置 j 為 0 則加位置 1 的路徑數(shù)量
                case 0:
                    ans = (ans + arr[1]) % mod
                //若位置 j 為 max 則加位置 max-1 的路徑數(shù)量
                case max:
                    ans = (ans + arr[max-1]) % mod
                //若位置 j 不為 0 或者 max 則加位置 j-1 和 j+1 的路徑數(shù)量
                default:
                    ans = (arr[j-1] + ans + arr[j+1]) % mod
                }
                //將 i 步到達(dá)位置 j 的路徑數(shù)量賦值到臨時數(shù)組的對應(yīng)位置
                temp[j]=ans
            }
            //將臨時i步到達(dá)的路徑數(shù)量數(shù)組賦值與 arr 以便求取 i+1 步到達(dá)路徑數(shù)組時用
            arr = temp
        }
        //遍歷結(jié)束后，arr 即為 steps 步可到達(dá)路徑數(shù)量數(shù)組，arr[0] 即為 steps 步到達(dá)位置 0 的路徑數(shù)量
        return arr[0]
    }

代碼地址：https://github.com/sinianshou/EGSwiftLearning