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