พีชคณิตที่ถูกต้องสำหรับลำดับ DI ใน C++

สมมติว่าเรามีสตริง S นี่คือสตริงของอักขระจากชุด {'D', 'I'} (D หมายถึง "ลดลง" และฉันหมายถึง "เพิ่มขึ้น")

ตอนนี้ให้พิจารณาว่าการเรียงสับเปลี่ยนที่ถูกต้องคือการเรียงสับเปลี่ยน P[0], P[1], ..., P[n] ของจำนวนเต็ม {0 ถึง n} เพื่อให้ i ทั้งหมดเป็นไปตามกฎเหล่านี้:

• ถ้า S[i] =='D' แล้ว P[i]> P[i+1];

• มิฉะนั้นเมื่อ S[i] =='I' แล้ว P[i]

เราต้องหาว่าการเรียงสับเปลี่ยนที่ถูกต้องมีกี่แบบ? คำตอบอาจมีขนาดใหญ่มาก ดังนั้นเราจะกลับมาใช้ mod 10^9 + 7

ดังนั้น หากอินพุตเป็นเหมือน "IDD" ผลลัพธ์จะเป็น 3 ดังนั้นจะมีการเรียงสับเปลี่ยนที่แตกต่างกันสามแบบ เหล่านี้คือ (0,3,2,1), (1,3,2,0), ( 2,3,1,0).

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

• n :=ขนาด S

• กำหนดขนาดอาร์เรย์ 2 มิติหนึ่ง dp (n + 1) x (n + 1)

• สำหรับการเริ่มต้น j :=0 เมื่อ j <=n อัปเดต (เพิ่ม j โดย 1) ทำ -

  • dp[0, j] :=1

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้า S[i] เหมือนกับ 'I' แล้ว −

    • สำหรับการเริ่มต้น j :=0, curr :=0, เมื่อ j

      • curr :=(dp[i, j] + curr) mod m

      • dp[i + 1, j] =(dp[i + 1, j] + curr)

  • อย่างอื่น

    • สำหรับการเริ่มต้น j :=n - i - 1, curr :=0 เมื่อ j>=0, อัปเดต (ลด j โดย 1) ทำ -

      • curr :=(dp[i, j + 1] + curr) mod m

      • dp[i + 1, j] =(dp[i + 1, j] + curr)

• กลับ dp[n, 0]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
   public:
   int numPermsDISequence(string S) {
      int n = S.size();
      vector<vector<int>> dp(n + 1, vector<int>(n + 1));
      for (int j = 0; j <= n; j++)
      dp[0][j] = 1;
      for (int i = 0; i < n; i++) {
         if (S[i] == 'I') {
            for (int j = 0, curr = 0; j < n - i; j++) {
               curr = (dp[i][j] + curr) % m;
               dp[i + 1][j] = (dp[i + 1][j] + curr) % m;
            }
         } else {
            for (int j = n - i - 1, curr = 0; j >= 0; j--) {
               curr = (dp[i][j + 1] + curr) % m;
               dp[i + 1][j] = (dp[i + 1][j] + curr) % m;
            }
         }
      }
      return dp[n][0];
   }
};
main(){
   Solution ob;
   cout << (ob.numPermsDISequence("IDD"));
}

อินพุต

"IDD"

ผลลัพธ์

3