C++ 中在若干步後停留在同一位置的方法數


假設有一個大小為 arrLen 的陣列,並且我們在該陣列的索引 0 處有一個指標。在每一步中,我們可以在陣列中向左移動 1 個位置,向右移動 1 個位置,或者停留在同一位置。

現在假設我們有兩個整數 steps 和 arrLen,我們必須找到指標在恰好 steps 步後仍然位於索引 0 的方法數。如果答案非常大,則將其返回模 10^9 + 7。

因此,如果輸入類似於 steps = 3,arrLen = 2,則輸出將為 4,因為有 4 種不同的方法可以在 3 步後停留在索引 0。這些是 [右,左,停留在原處],[停留在原處,右,左],[右,停留在原處,左],[停留在原處,停留在原處,停留在原處]。

為了解決這個問題,我們將遵循以下步驟 -

  • m := 1e9 + 7

  • 定義一個函式 add(),它將接收 a、b,

  • 返回 (a mod m + b mod m) mod m

  • 定義一個二維陣列 dp

  • 定義一個函式 solve(),它將接收 n、x、pos 並將其初始化為 0,

  • 如果 x 等於 0,則 -

    • 當 pos 等於 0 時返回 true

  • 如果 dp[pos, n] 不等於 -1,則 -

    • 返回 dp[pos, n]

  • ans := 0

  • 如果 pos > 0,則

    • ans := add(ans, solve(n, x - 1, pos - 1))

  • 如果 pos < n - 1,則 -

    • ans := add(ans, solve(n, x - 1, pos + 1))

  • ans := add(ans, solve(n, x - 1, pos))

  • dp[pos, n] := ans

  • 返回 ans

  • 從主方法執行以下操作 -

  • x := arrLen 和 steps / 2 + 1 的最小值

  • dp := 定義一個大小為 2 x (x + 1) 的二維陣列,用 0 填充它

  • dp[0, 0] := 1

  • n := arrLen

  • 對於初始化 i := 1,當 i <= steps 時,更新(i 增加 1),執行 -

    • 對於初始化 j := 0,當 j < arrLen 和 step/2 + 1 的最小值時,更新(j 增加 1),執行 -

      • x := (i - 1) mod 2

      • y := i mod 2

      • dp[y, j] := dp[x, j]

      • 如果 j - 1 >= 0,則 -

        • dp[y, j] := add(dp[y, j], dp[x, j - 1])

      • 如果 j + 1 < n,則 -

        • dp[y, j] := add(dp[y, j], dp[x, j + 1])

  • 返回 dp[steps mod 2, 0]

讓我們看看以下實現以獲得更好的理解 -

示例

 即時演示

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MOD = 1e9 + 7;
lli add(lli a, lli b){
   return (a % MOD + b % MOD) % MOD;
}
class Solution {
   public:
   vector<vector<int> > dp;
   int solve(int n, int x, int pos = 0){
      if (x == 0) {
         return pos == 0;
      }
      if (dp[pos][n] != -1)
      return dp[pos][n];
      int ans = 0;
      if (pos > 0)
      ans = add(ans, solve(n, x - 1, pos - 1));
      if (pos < n - 1)
      ans = add(ans, solve(n, x - 1, pos + 1));
      ans = add(ans, solve(n, x - 1, pos));
      dp[pos][n] = ans;
      return ans;
   }
   int numWays(int steps, int arrLen){
      int x = min(arrLen, steps / 2 + 1);
      this->dp = vector<vector<int> >(2, vector<int>(x + 1, 0));
      dp[0][0] = 1;
      int n = arrLen;
      for (int i = 1; i <= steps; i++) {
         for (int j = 0; j < min(arrLen, steps / 2 + 1); j++) {
            int x = (i - 1) % 2;
            int y = i % 2;
            dp[y][j] = dp[x][j];
            if (j - 1 >= 0)
            dp[y][j] = add(dp[y][j], dp[x][j - 1]);
            if (j + 1 < n)
            dp[y][j] = add(dp[y][j], dp[x][j + 1]);
         }
      }
      return dp[steps % 2][0];
   }
};
main(){
   Solution ob;
   cout << (ob.numWays(3,2));
}

輸入

3, 2

輸出

4

更新於: 2020年6月8日

208 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告