Số cách ở cùng một chỗ sau một số bước trong C ++

Giả sử có một mảng kích thước arrLen và chúng ta cũng có một con trỏ ở chỉ số 0 trong mảng đó. Tại mỗi bước, chúng ta có thể di chuyển 1 vị trí sang trái, 1 vị trí sang phải trong mảng hoặc giữ nguyên vị trí.

Bây giờ, giả sử chúng ta có hai bước số nguyên và arrLen, chúng ta phải tìm số cách sao cho con trỏ vẫn ở chỉ mục 0 sau chính xác các bước. Nếu câu trả lời là rất lớn thì hãy trả về nó theo mô-đun 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như các bước =3, arrLen =2, thì đầu ra sẽ là 4, vì có 4 cách khác nhau để giữ nguyên chỉ số 0 sau 3 bước. Đó là [Bên phải, Bên trái, Ở lại], [Ở lại, Bên phải, Bên trái], [Bên phải, Ở lại, Bên trái], [Ở lại, Ở lại, Ở lại].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

m:=1e9 + 7
Xác định một hàm add (), điều này sẽ lấy a, b,
return (a mod m + b mod m) mod m
Xác định một dp mảng 2D
Xác định một hàm giải quyết (), điều này sẽ lấy n, x, pos khởi tạo nó bằng 0,
nếu x giống 0 thì -
- trả về true khi pos giống 0
nếu dp [pos, n] không bằng -1 thì -
- trả về dp [pos, n]
ans:=0
nếu pos> 0 thì
- ans:=add (ans, giải quyết (n, x - 1, pos - 1))
nếu pos
- ans:=add (ans, giải quyết (n, x - 1, pos + 1))
ans:=add (ans, giải quyết (n, x - 1, pos))
dp [pos, n]:=ans
trả lại ans
Từ phương thức chính, hãy làm như sau -
x:=tối thiểu arrLen và các bước / 2 + 1
dp:=Xác định một mảng 2D có kích thước 2 x (x + 1), điền vào mảng này bằng 0
dp [0, 0]:=1
n:=arrLen
để khởi tạo i:=1, khi tôi <=bước, cập nhật (tăng i lên 1), thực hiện -
- để khởi tạo j:=0, khi j
  - x:=(i - 1) mod 2
  - y:=i mod 2
  - dp [y, j]:=dp [x, j]
  - nếu j - 1> =0, thì -
    - dp [y, j]:=add (dp [y, j], dp [x, j - 1])
  - nếu j + 1
    - dp [y, j]:=add (dp [y, j], dp [x, j + 1])
return dp [bước mod 2, 0]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

3, 2

Số cách ở cùng một chỗ sau một số bước trong C ++

Ví dụ

Đầu vào

Đầu ra