Restore The Array trong C++

Chuỗi s là nối các số của mảng A (không có dấu cách), mỗi phần tử 1..k. Đếm số cách khôi phục mảng A. Kết quả modulo 10^9+7.

Ví dụ: s="1318", k=2000 → 8 cách: [1318], [131,8], [13,18], [1,318], [1,3,18], [1,31,8], [13,1,8], [1,3,1,8].

Giải thuật (DP)

DP[i] = số cách khôi phục tiền tố s[0..i-1]. Duyệt i từ 1..n, thử độ dài đoạn cuối từ 1 đến 10 (vì k ≤ 10^9). Nếu đoạn hợp lệ (không dẫn 0, giá trị ≤ k) → DP[i] += DP[i-len].

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const int MOD = 1e9 + 7;

class Solution {
    int add(int a, int b) { return (a + b) % MOD; }
public:
    int numberOfArrays(string s, int k) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        string ks = to_string(k);
        
        for (int i = 1; i <= n; i++) {
            string cur = "";
            for (int j = i; j >= 1 && i - j + 1 <= 10; j--) {
                cur = s[j-1] + cur;
                if (s[j-1] == '0') continue; // không cho phép dẫn 0
                if (cur.size() > ks.size()) break;
                if (cur.size() == ks.size() && cur > ks) break;
                int val = stoi(cur);
                if (val >= 1 && val <= k)
                    dp[i] = add(dp[i], dp[j-1]);
            }
        }
        return dp[n];
    }
};

int main() {
    Solution ob;
    cout << ob.numberOfArrays("1318", 2000); // 8
    return 0;
}

Đầu vào / Đầu ra

Input: "1318", 2000
Output: 8