จำนวนวิธีที่จะอยู่ในที่เดียวกันหลังจากทำตามขั้นตอนบางอย่างใน C++

สมมติว่ามีอาร์เรย์ขนาด arrLen และเรายังมีตัวชี้ที่ดัชนี 0 ในอาร์เรย์นั้น ในแต่ละขั้นตอน เราสามารถย้าย 1 ตำแหน่งไปทางซ้าย 1 ตำแหน่งไปทางขวาในอาร์เรย์หรืออยู่ในตำแหน่งเดิม

สมมติว่าเรามีจำนวนเต็มสองขั้นตอนและ arrLen เราต้องหาจำนวนวิธีที่พอยน์เตอร์ยังคงอยู่ที่ดัชนี 0 หลังจากทำตามขั้นตอนทั้งหมด หากคำตอบมีขนาดใหญ่มาก ให้ส่งคืนโมดูล 10^9 + 7

ดังนั้น หากอินพุตเหมือนกับขั้นตอน =3, arrLen =2 ผลลัพธ์จะเป็น 4 เนื่องจากมี 4 วิธีที่แตกต่างกันในการคงค่าดัชนี 0 หลังจาก 3 ขั้นตอน เหล่านี้คือ [ขวา ซ้าย อยู่] [อยู่ ขวา ซ้าย] [ขวา อยู่ ซ้าย] [อยู่ อยู่ อยู่]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=1e9 + 7

• กำหนดฟังก์ชัน add() ซึ่งจะใช้เวลา a, b,

• กลับ (a mod m + b mod m) mod m

• กำหนดอาร์เรย์ 2 มิติหนึ่ง dp

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้เวลา n, x, pos เริ่มต้นด้วย 0

• ถ้า x เท่ากับ 0 แล้ว −

  • คืนค่า จริง เมื่อ pos เหมือนกับ 0

• ถ้า dp[pos, n] ไม่เท่ากับ -1 แล้ว −

  • กลับ dp[pos, n]

• ตอบ :=0

• ถ้า pos> 0 แล้ว

  • ans :=เพิ่ม (ตอบ, แก้ (n, x - 1, pos - 1))

• ถ้า pos

  • ans :=เพิ่ม (ตอบ, แก้ (n, x - 1, pos + 1))

• ans :=เพิ่ม (ตอบ, แก้ (n, x - 1, pos))

• dp[pos, n] :=ans

• กลับมาอีกครั้ง

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• x :=ขั้นต่ำของ arrLen และขั้นตอน / 2 + 1

• dp :=กำหนดอาร์เรย์ 2 มิติขนาด 2 x (x + 1) หนึ่งชุด เติมด้วย 0

• dp[0, 0] :=1

• n :=arrLen

• สำหรับการเริ่มต้น i :=1 เมื่อ i <=ขั้นตอน ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <ขั้นต่ำของ arrLen และขั้นตอนที่ 2 + 1 อัปเดต (เพิ่ม j ขึ้น 1) ให้ทำ -

    • x :=(i - 1) mod 2

    • y :=ฉัน mod 2

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

    • ถ้า j - 1>=0 แล้ว −

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

    • ถ้า j + 1

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

• กลับ dp[ขั้นตอน 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