Có một câu chuyện như thế này. Có một thanh niên đang ngồi cày quy hoạch động, cày miết, rồi ảnh cũng vui vì cuối cùng cũng có thể cày vài ba cái bài toán kinh điển và áp dụng được đôi chút. Chưa kịp thở phào nhẹ nhõm thì... BÙM! Thầy giáo của anh ném vào mặt anh chuyên đề "quy hoạch động chữ số", và trong khi bạn của anh ta ngồi cày vèo vèo, thì anh ấy... đang đau khổ tìm hiểu và chật vật với nó thật sự. Tới nỗi mà anh ta phải viết ra cái cuốn này cơ mà!

Và rồi tới bây giờ, với tư cách là chủ nhân của trang "Lập trình mất não", chủ đề đầu tiên mà anh ta sẽ viết là về... quy hoạch động chữ số, như bạn đã thấy.

(Nhìn là biết ếu chuyên nghiệp rồi, bố nào đi viết trên Wattpad?)

Có thể nói rằng quy hoạch động chữ số là một trong những dạng quy hoạch động rất hữu dụng khi bạn phải làm việc với những con số. Các dạng bài toán liên quan tới chữ số như "có bao nhiêu số trong đoạn l tới r mà không có con số x" hay "bạn hãy tính tổng của tất cả các chữ số của các số từ a tới b" thì thật sự nó sẽ là phao cứu sinh cho mọi người.

Và mục đích của nó để chiến đấu với các con số. Phải, chiến đấu với nó thôi.

Vậy thật sự bạn sẽ làm gì với... quy hoạch động chữ số?

Thật sự nếu bạn không biết gì về quy hoạch động mà vẫn đang đọc cái này thì nên lên mạng, lên VNOI Wiki, hay lên trang nào về quy hoạch động, đọc và nghiền ngẫm nó, trước khi đọc cái bài viết mất não này của Solra.

Rồi, ta vào guồng.

PHẦN I: GIẢI THÍCH VỀ QUY HOẠCH ĐỘNG CHỮ SỐ

Lên mạng, bạn hẳn phải đang đọc những tài liệu tiếng Anh mà có thể vì lí do dịch thuật nên bạn chưa hiểu bản chất vấn đề (ừ thì tôi viết bài này để tôi hiểu bản chất vấn đề mà), hay là việc bạn đơn giản hỏi "dp[pos][cnt][flag] là cái gì", rồi "sao nó tận mảng ít nhất là 3 chiều thế này?".

Trước tiên ta vẫn phải vào thứ gọi là bài toán đặt ra, cái phần này bố nào chả biết.

"Tính tổng các chữ số từ 1 tới n".

Để giải thích đề, giả dụ bạn có n = 10, thì bạn sẽ phải tính tổng như này:

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 1 + 0 = 46.

Rồi bạn xuất ra số 46.

Với cái giới hạn 10^7 hay 10^8 thì bố nào làm khó được bạn luôn. Đơn giản thôi, một vòng for chạy từ 1 tới n, rồi tính tổng các chữ số của nó, rồi cộng lại. Giờ mà bạn không biết phân tích tổng các chữ số của một số nữa thì ban tìm nhầm trang rồi XD.

Vậy có cách nào tối ưu hơn không? Giả như tôi cho 10^18 là bạn chết ngắc ngay! (trừ khi đó là những người đã biết về cái loại này và rồi vả cho tôi nổ đom đóm mắt). Từ đó, quy hoạch động chữ số ra đời.

Để bắt đầu, ta hãy cùng phân tích một số bất kì, giả như tui đặt a bằng với...

843953.

Việc bạn cần làm lúc này là hãy thử ghép các chữ số lại vào với nhau, sao cho bạn nhận được một số nhỏ hơn 843953. Chứ nếu mà in ra có bao nhiều số thì... tôi nghĩ bài này nó quá đơn giản rồi.

Hmm...

Trước tiên, đây sẽ là khái niệm cho vị trí Pos. Pos ở đây là vị trí chữ số bạn đang xét, tính từ trái qua phải, và tôi sẽ mặc định nó là từ 1, để cho nó thuận với tư duy con người (chúng ta đâu phải là những cái máy nhỉ XD).

Thí dụ Pos = 1 thì bạn đang xét số 8, Pos = 4 thì bạn đang xét số 9, tất nhiên là với con số tôi cho ví dụ.

Vậy với Pos = 1, bạn có thể chọn các chữ số nào từ 0 đến 9? Tất nhiên bạn không thể chọn tất cả vì số cuối cùng bạn nhận được phải nhỏ hơn con số kia, mà cùng một số chữ số thì tôi đó bạn tìm được cặp (a,b) sao cho a <= b và chữ số đầu tiên của a lại lớn hơn chữ số đầu tiên của b đấy.

Vì vậy, ta giả sử số ta cần là c, vậy thì c[Pos] (tức vị trí chữ số thứ Pos trong c) cần phải nhỏ hơn hoặc bằng với 8, hay nếu bạn chưa quên a = 843953, thì c[Pos] <= a[Pos].

Well, tất nhiên nó không áp dụng cho tất cả chữ số rồi. Bạn có thể lấy ngoại lệ là 799999 chẳng hạn, thì không phải tất cả các vị trí a[Pos] đều lớn hơn hoặc bằng c[Pos], nhưng c vẫn nhỏ hơn a.

Tới nước này, Flag phát huy sức mạnh của mình. Bạn có thể để ý rằng...

------> Nếu a[pos] = c[pos], thì để thỏa mãn c < a, c[pos + 1] sẽ nhỏ hơn hoặc bằng a[pos + 1]

(Tức nếu c[1] = 8, thì c[2] <= 4 chẳng hạn)

------> Nếu a[pos] > c[pos], thì tất tần tật các c[pos + x] sau đó đều có thể tự do chọn các số từ 0 tới 9.

Và đơn giản chỉ cần 1 vị trí pos nào đó mà a[pos] > c[pos], thì các c[pos + x] đều sẽ không phụ thuộc vào các a[pos + x] tương ứng.

Hay nếu tôi nói khó hiểu vãi cả đái thì nói thế này cho dễ. Ta biết được một chữ số chỉ có thể chọn từ 0 tới 9, nên có ràng buộc hay không, giới hạn (limit) của chữ số đó cũng chỉ tới 9 là hết đát.

Nhưng khi trước một pos nào đó không có thằng nội x nào thỏa mãn a[pos - x] > c[pos - x] thì limit của c[pos] vẫn sẽ chỉ là a[pos].

Đặt limit của c[pos] là limit(c[pos]), nói cách khác:

--------> Nếu tồn tại x sao cho a[pos - x] > c[pos - x] thì limit(c[pos]) = 9.

--------> Ngược lại, limit(c[pos]) = a[pos].

Rồi bạn đang hỏi: "FLAG CỦA MÀY Ở ĐÂU HẢ THẰNG SOL CỜ HÓ???". 

Flag đây Flag đây! Mình đâu phải thuyết trình tràn lan đại hải về cái việc a[pos - x] rồi c[pos] với limit = 9 để trưng bày cho không đâu! Ở đây ta đã có được 

DP[pos][flag]

Vậy nếu pos là vị trí của chữ số ta đang xét, thì Flag thực ra lại là kiểm tra coi trước chữ số đó có có tồn tại trường hợp (a[pos - x] > c[pos - x]) hay không! Trạng thái của Flag được định hình là 1 nếu có tồn tại, và 0 nếu không tồn tại. Với Flag = 1, quất cái limit(c[pos]) = 9, còn với Flag = 0 thì... tự biết đi nhá XD. (Chứ không đọc kĩ rồi lại chất vấn ông đã nói đâu thì tôi xin bó tay chấm com)

Vậy là ta đã kinh qua chặng đường "tìm các số nhỏ hơn hoặc bằng 843953" hay nói chung hơn là tìm các số nhỏ hơn hoặc bằng n.

Đến lúc này các bạn đang hỏi [cnt] ở đâu...

PHẦN SAU NHÁ!