โปรแกรมนับวิธีแบ่งสตริงตัวเลขเป็นรายการค่าที่อยู่ในช่วง 1 ถึง k ใน Python

คำอธิบายโจทย์

ให้สตริง s ประกอบด้วยตัวเลข 0-9 และค่า k หาจำนวนวิธีแตก s เป็นรายการตัวเลขที่ทุกตัวอยู่ใน [1, k] ผลลัพธ์ mod 10^9+7

ตัวอย่าง

s = "3456", k = 500 → เอาต์พุต: 7
วิธี: [3,4,5,6], [34,5,6], [3,4,56], [3,45,6], [34,56], [345,6], [3,456]

วิธีแก้ปัญหา

Dynamic Programming แบบ Bottom-up:

dp[i] = จำนวนวิธีแตก substring s[i:]
dp[n] = 1 (base case)
จาก i = n-1 ถึง 0: สร้างตัวเลข curr_val จาก s[i:j+1] ทีละหลัก
ถ้า 1 ≤ curr_val ≤ k: dp[i] += dp[j+1]
ถ้า curr_val > k: break (เพราะเพิ่มหลักจะใหญ่ขึ้นเรื่อยๆ)

โค้ด Python

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))

อินพุต

"3456", 500