Cho một chuỗi số dài N: 400 <= N <= 5000
Hỏi có bao nhiêu cách tách chuỗi số đó thành các chuỗi con sao cho các chuỗi tách vẫn giữ nguyên vị chí và dãy con đó thành dãy không giảm. Và không có chuỗi số con nào có số 0 đứng ở đầu
VD:
Input: 111
Output: 2
Note: {1,11}; {111}
Input: 21023
Output: 3
Note: {2,10,23}; {2,1023}; {21023}
Yêu cầu thuật toán tối thiểu O(n^2). Cao thủ nào giúp em chỉ em cái công thức quy hoạch động cũng được ạ, còn lại em tự tối ưu sau
Update 02/05/2020
Mình tìm công thức quy hoạch động như này không chắc chuẩn chưa và thuật của mình là O(n^4) được 50%. dp[số lượng dấu phẩy][độ dài chuỗi số xét]; Rồi mình tách ra thành hai trường hợp: 1 trường hợp số cuối luôn luôn lơn hơn các số sau, trường hợp có thể số cuối lớn số gần nó hoặc không
dp[i][j] = 0;
//Trường hợp 1 số cuối luôn luôn lớn hơn
for g = i -> j - f(j)
dp[i][j] += dp[i-1][g];
//Số cuối có thể lơn hơn hoặc không
for g = j - f(j) + 1 -> j - g(j)
dp[i][j] += Hàm_lấy_tất cả_các_dp[i-1][g]_không_có số nào cạnh nó lớn hơn maxdp[i][j];
Mình không chắc là có công thức khác không hay là công thức chuẩn rồi và chỉ việc tối ưu
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?