QHD f[i,j,k], i vị trí chữ số đang xét, j là trạng thái đánh dấu số nào đã xuất hiện hơn 1 lần k,  để kiểm tra số đang xét <r hay 0? . DPT: n là số chữ số, O(n*2^10*10*2) (2^10*2 số trạng thái, 10 là chi phí chuyển trạng thái)

Bạn nên viết rõ ràng hơn nhé như hàm số có ý nghĩa như thế nào. Chuyển trạng thái như thế nào. "< r" là thế nào. Đừng bình luận thiếu trách nhiệm như vậy. Thuật toán của bạn có vẻ không ổn. Thứ nhất làm sao biết số đó xuất hiện hay chưa nếu bit 1 là để cho những số đã xuất hiện một lần vậy làm sao biết được số nào xuất hiện hơn một lần ? Thứ 2: đề bài là tìm trong đoạn từ x tới y vậy một tham số k là đã đủ ? 

Xác định hàm số

Anyway, về cơ bản hướng đi thuật toán trên khá ổn nhưng suy nghĩ chưa được thấu đáo. Sau đây mình sẽ nói rõ hơn thuật toán của bài này. Lưu ý các chữ số trong một số sẽ được đánh số thứ tự từ trái sang phải bắt đầu từ 1. Và một điều nữa là nếu số chữ số của x nhỏ hơn y thì thêm số không vào đầu của x để có được số lượng chữ số bằng nhau. Một số ký hiệu: \(len(y)\) là số lượng chữ số của số y và dĩ nhiên sau khi thêm số không vào đầu số x thì \(len(x) = len(y)\) .

Ta có: \(F[i, S, ok1, ok2]\) mang ý nghĩa là số lượng những số may mắn alpha nằm trong đoạn [x, y] thỏa mãn:

• \(ok1 = True\) nếu alpha có \(i\) chữ số đầu tiên nhỏ hơn \(i\) chữ số dầu tiên của y còn ngược lại thì alpha có \(i\) chữ số đầu tiên bằng \(i\) chữ số đầu tiên của y.
• \(ok2 = True\) nếu alpha có \(i\) chữ số đầu tiên lớn hơn \(i\) chữ số đầu tiên của x còn ngược lại thì alpha có \(i\) chữ số đầu tiên bằng \(i\) chứ số đầu tiên của x.
• \(S\) là một dãy tam phân độ dài 10 có nghĩa là một dãy các chữ số từ 0 -> 2. Ta đánh só thứ tự các chữ số trong s từ 0 tới 9. Chữ số thứ k trong dãy:
  • sẽ là 0 nếu chữ số k không tồn tại trong \(i\)chữ số đầu tiên của alpha
  • sẽ là 1 nếu chữ số k xuất hiện một lần trong \(i\)chữ số đầu tiên của alpha
  • sẽ là 2 nếu chữ số k xuất hiện nhiều hơn một lần trong \(i\) chữ số đầu tiên của alpha

Ta thấy rõ ràng kết quả sẽ là \(F[0,'0000000000', False, False]\) 

Xác định công thức truy hồi

Bây giờ ta sẽ đi vào tính công thức truy hồi cho bài toán.

Ta có: \(F[i, S, ok1, ok2]\) = Tổng của \(F[i+1, S_d, ok1_d, ok2_d]\) với d chạy từ \(L\) tới \(R\). Với việc giả sử chữ số thứ i+1 là d thì ta sẽ tính được \(S_d, ok1_d, ok2_d\) từ \(S, ok1, ok2\). Lưu ý \(L\) và \(R\) phụ thuộc vào 2 biến \(ok1\) và \(ok2\). Ví dụ nếu \(ok1\) bằng \(True\) tất là \(i\) chữ số đầu của alpha nhỏ hơn \(i\) chữ số đầu của y thì chữ số \(i+1\) là gì đi nữa thì alpha cũng sẽ nhỏ hơn y. Nhưng nếu \(ok1\) bằng \(False\) tất là \(i\) chữ số đầu của alpha bằng \(i\) chữ số đầu của y thì chữ số \(i+1\) của alpha không được vượt quá chữ số \(i+1\) của y. Tương tự với \(ok2\).

Xác định bài toán cơ bản

Như vậy bây giờ ta đã có công thức rồi. Ta sẽ đi xác định bài toán cơ bản. Bài toán cơ bản đó là: \(F[len(y), S, ok1, ok2]\). Tính giá trị bài toán cơ bản như sau:

\(F[len(y), S, ok1, ok2] = 1\) nếu tồn tại chữ số 1 trong dãy tam phân \(S\). Ngược lại thì sẽ có giá trị là 0.

Xác định thứ tự duyệt các trạng thái

Giờ nhìn vào ta sẽ thấy cách đơn giản nhất để tính là dùng đệ quy có nhớ. Tất là nếu mình đã đệ quy vào tính \(F[i, S, ok1, ok2]\) thì đánh dấu lại là đã tính để lần sau mình lấy kết quả tính được luôn không cần phải đệ quy vào để tính thêm.

Tối ưu thuật toán

Trong thuật toán trên có một vấn đề khuất mắt đó là cách lưu trữ tham số \(S\). Nếu lưu là chuỗi sẽ khá không thuận tiện. Nếu chia ra thành 10 tham biến mỗi biến từ 0->2 thì sẽ làm tăng chiều của mảng \(F\). Mảng càng nhiều chiều thì việc truy cập vào một phần tử của mảng càng lâu. Một phương pháp để giải quyết vấn đề này ta sẽ mã hóa dãy tam phân \(S\) thành một số thập phân.

Nếu cài đặt theo thuật toán này thì dpt sẽ không vượt quá \(O(len(y)*3^{10}*2*2*10)\)

:v thực ra anh thấy trả lời vậy cũng ok mà. Nhiều khi mình ko có thời gian, viết 1 2 dòng ngắn gọn về ý tưởng cách làm vào cũng tốt cho forum. Nếu bạn hỏi bài vẫn ko hiểu thì có thể hỏi tiếp :D

Em thấy cmt cua bạn tuanbi phía trên. Đối với những người đã biết kiểu công thức QHD này đọc vào thì có thể có ích. Nhưng với người chưa biết đọc vào sẽ chẳng hiểu thằng này nó đang nói cái gì. Ít nhất cũng phải nếu được ý nghĩa hàm số.

À mà cái đoạn 2 biến ok1, ok2 của em thực ra chỉ cần dùng 1 biến là đủ nhé :v

Số số trong đoạn [x, y] = (số số trong đoạn [1, y]) - (số số trong đoạn [1, x-1])

--> quy bài toán ban đầu về bài đếm số số trong đoạn [1, y]

--> chỉ cần 1 biến ok để xác định là nó đã nhỏ hơn cận trên hay chưa.