Chương trình đếm số cách tách chuỗi số thành danh sách giá trị trong Python

Cho chuỗi s chỉ chứa chữ số 0-9 và số k. Đếm số cách biểu diễn s dưới dạng danh sách các số từ [1, k]. Kết quả modulo 10^9+7.

Ví dụ: s = "3456", k = 500 → 7 cách: [3,4,5,6], [34,5,6], [3,4,56], [3,45,6], [34,56], [345,6], [3,456].

Giải pháp

Quy hoạch động (DP) từ cuối về đầu:

• dp[i] = số cách tách chuỗi con s[i:]
• dp[n] = 1 (chuỗi rỗng)
• Duyệt i từ n-1 về 0, xây dựng curr_val bằng cách thêm chữ số lần lượt
• Nếu 1 ≤ curr_val ≤ k: dp[i] = (dp[i] + dp[j+1]) % MOD
• Nếu curr_val > k: break (vì thêm chữ số chỉ làm tăng giá trị)

Ví dụ minh họa

class Solution:
    def solve(self, s, k):
        m = 10 ** 9 + 7
        N = len(s)
        dp = [0] * (N + 1)
        dp[N] = 1
        for i in range(N - 1, -1, -1):
            curr_val = 0
            for j in range(i, N):
                curr_val = curr_val * 10 + int(s[j])
                if 1 <= curr_val <= k:
                    dp[i] = (dp[i] + dp[j + 1]) % m
                else:
                    break
        return dp[0]

ob = Solution()
s = "3456"
k = 500
print(ob.solve(s, k))

Đầu vào

"3456", 500

Đầu ra

7