Cấu trúc dữ liệu và Giải thuật Bài 65: Lập trình động chữ số (Digit DP) - Đếm và tối ưu hóa trên dãy số lớn.

Tiếp tục hành trình khám phá Lập trình động nâng cao (Chương 14), chúng ta đối mặt với một lớp bài toán cực kỳ phổ biến trong các hệ thống phân tích dữ liệu quy mô lớn và bảo mật: Bài toán đếm số lượng thỏa mãn điều kiện trên một khoảng số nguyên khổng lồ.

Ví dụ: "Hãy đếm xem có bao nhiêu số nằm trong khoảng từ $1$ đến $10^{18}$ sao cho tổng các chữ số của nó chia hết cho một số $K$, hoặc không chứa chữ số 4 và 7 (con số may mắn/xui xẻo trong tài chính)".

Nếu bạn sử dụng vòng lặp vét cạn (Brute-force) từ $1$ đến $10^{18}$, chương trình sẽ phải chạy qua một tỷ tỷ vòng lặp, khiến siêu máy tính cũng phải đầu hàng vì tốn hàng ngàn năm tính toán. Để giải quyết các bài toán thao tác trên từng chữ số (digits) của các con số siêu lớn, kỹ thuật Digit DP (Digit Dynamic Programming) ra đời như một vị cứu tinh.

1. Bản chất của Digit DP và Tư duy "Xây dựng số từ trái sang phải"

Digit DP áp dụng mô hình xây dựng con số giống như cách con người viết một số tự nhiên: Viết từ trái qua phải (từ hàng cao nhất xuống hàng đơn vị).

Bất kỳ số nguyên dương nào cũng có thể được phân rã thành một chuỗi các chữ số $[d_1, d_2, d_3, \dots, d_m]$. Thay vì xử lý nguyên một con số lớn, Lập trình động sẽ bóc tách nó thành từng chữ số độc lập.

Tuy nhiên, bài toán đặt ra là làm thế nào để đảm bảo con số ta đang xây dựng không vượt quá giới hạn $N$ cho trước? Đây là lúc hai vũ khí cốt lõi của Digit DP xuất hiện:

1. Mảng Chuyển đổi (Conversion to Range): Bài toán tìm số lượng trong khoảng $[A, B]$ luôn được quy đổi thành hiệu của hai hàm đếm từ $0$ đến $B$ trừ đi từ $0$ đến $A-1$: Solve(B) - Solve(A - 1).

2. Cờ Giới hạn (The Tight Flag): Trạng thái quan trọng nhất trong mọi thuật toán Digit DP. Cờ tight (nhận giá trị true hoặc false) cho biết ta có đang bị kẹp bởi biên của số $N$ hay không:

   • Nếu tight = true: Các chữ số tiếp theo bạn chọn không được phép vượt quá chữ số tương ứng tại vị trí đó của $N$.

   • Nếu tight = false: Bạn đã chọn một chữ số nhỏ hơn $N$ ở các bước trước đó, do đó các chữ số tiếp theo được tự do hoàn toàn chọn từ 0 đến 9.

2. Mô hình Trạng thái (State Definition)

Một hàm Digit DP tổng quát thường nhận các tham số trạng thái sau:

• idx: Vị trí của chữ số đang xét (từ trái qua phải, bắt đầu từ 0 đến độ dài của chuỗi số $N$).

• tight: Cờ boolean kiểm tra tính giới hạn biên.

• sum (hoặc các biến trạng thái phụ thuộc bài toán): Tổng các chữ số đã chọn, số lượng chữ số đã xuất hiện, v.v.

Bảng nhớ đệm (Memoization table) sẽ lưu trữ kết quả của các trạng thái dp[idx][tight][sum...] để tránh việc tính toán lặp lại các nhánh con giống hệt nhau.

3. Triển khai Mẫu Digit DP bằng Golang

Dưới đây là mã nguồn chuẩn mực giải quyết bài toán kinh điển: Đếm số lượng các số nguyên từ $1$ đến $N$ có tổng các chữ số bằng một giá trị cố định $S$.

Go

package main

import (
	"fmt"
	"strconv"
)

// Hàm chuyển số N thành mảng các chữ số để dễ xử lý
func getDigits(n int64) []int {
	s := strconv.FormatInt(n, 10)
	digits := make([]int, len(s))
	for i, ch := range s {
		digits[i] = int(ch - '0')
	}
	return digits
}

// Hàm Digit DP cốt lõi
// idx: vị trí hiện tại
// tight: có đang bị giới hạn bởi biên của số N hay không
// currentSum: tổng các chữ số đã chọn tính đến thời điểm hiện tại
// targetSum: tổng mục tiêu cần đạt được
// digits: mảng các chữ số của N
// memo: bảng ghi nhớ (Memoization table)
func countWithDigitSum(idx int, tight bool, currentSum int, targetSum int, digits []int, memo map[string]int) int {
	// Trường hợp cơ sở: Đã duyệt qua tất cả các chữ số
	if idx == len(digits) {
		if currentSum == targetSum {
			return 1 // Thỏa mãn điều kiện tổng chữ số bằng targetSum
		}
		return 0
	}

	// Tạo khóa duy nhất cho bảng Memoization
	// (Trong thực tế production, có thể tối ưu khóa này bằng mảng đa chiều)
	memoKey := fmt.Sprintf("%d-%t-%d", idx, tight, currentSum)
	if val, exists := memo[memoKey]; exists {
		return val
	}

	// Xác định giới hạn trên cho chữ số tại vị trí idx
	limit := 9
	if tight {
		limit = digits[idx]
	}

	totalCount := 0

	// Thử lần lượt các chữ số từ 0 đến limit
	for digit := 0; digit <= limit; digit++ {
		// Xác định cờ tight cho bước tiếp theo:
		// Nếu trước đó đang tight và chữ số hiện tại bằng giới hạn max, bước sau vẫn tiếp tục tight.
		nextTight := tight && (digit == limit)

		// Gọi đệ quy chuyển sang chữ số tiếp theo
		totalCount += countWithDigitSum(idx+1, nextTight, currentSum+digit, targetSum, digits, memo)
	}

	// Lưu vào bảng nhớ trước khi trả về
	memo[memoKey] = totalCount
	return totalCount
}

// Hàm giải quyết bài toán đếm từ 1 đến N có tổng chữ số bằng S
func SolveDigitDP(n int64, targetSum int) int {
	if n < 0 {
		return 0
	}
	digits := getDigits(n)
	memo := make(map[string]int)
	return countWithDigitSum(0, true, 0, targetSum, digits, memo)
}

func main() {
	var n int64 = 1000 // Ví dụ: Xét từ 1 đến 1000
	targetSum := 10     // Đếm các số có tổng chữ số bằng 10

	result := SolveDigitDP(n, targetSum)
	fmt.Printf("Số lượng số từ 1 đến %d có tổng chữ số bằng %d là: %d\n", n, targetSum, result)
}

4. Phân tích Hiệu năng (Big-O)

• Thời gian (Time Complexity): $O(D \cdot 9 \cdot S)$ (với $D$ là số lượng chữ số của $N$, ví dụ $D = 18$ với $10^{18}$, và $S$ là tổng chữ số tối đa). Nhờ cơ chế Memoization, các trạng thái trùng lặp được cắt tỉa hoàn toàn, giúp thời gian thực thi giảm từ cấp số nhân xuống tuyến tính cực nhanh (chỉ vài mili-giây).

• Không gian (Space Complexity): $O(D \cdot S)$ để lưu trữ bảng Memoization, cực kỳ tiết kiệm bộ nhớ phần cứng.

5. Ứng dụng Thực tế trong Hệ thống Enterprise

Digit DP không chỉ là công cụ giải thuật toán học mà còn giải quyết nhiều bài toán kỹ thuật thực tế:

• Hệ thống Phát hiện Gian lận Tài chính & Giao dịch (Fraud Detection): Quét qua hàng triệu mã giao dịch hoặc số tài khoản ngân hàng có cấu trúc lớn để lọc ra các dãy số thỏa mãn các quy luật đặc thù hoặc chứa các mẫu số đáng ngờ phục vụ kiểm toán bảo mật.

• Kiểm tra và Xác thực Khóa Định danh (ID/SKU Validation): Kiểm tra xem các mã SKU sản phẩm hoặc mã định danh người dùng có thỏa mãn các ràng buộc toán học phức tạp (như tổng mã hóa, quy tắc chữ số kiểm tra) trên không gian dữ liệu khổng lồ mà không cần quét cơ sở dữ liệu tốn kém.

• Mật mã học và Phân tích Mẫu số (Cryptography): Phân tích các đặc tính phân phối số học của các dãy số nguyên tố hoặc khóa mã hóa trong một dải giá trị giới hạn.

Sự sắc bén của Digit DP giúp chúng ta kiểm soát hoàn toàn các không gian số học khổng lồ. Trong bài học tiếp theo, chúng ta sẽ tiếp tục khám phá các kỹ thuật tối ưu hóa trạng thái Lập trình động sâu hơn để xử lý các đồ thị hình học phức tạp.