Toi uu Knuth cho DP chia doan. opt[i][j] = diem chia toi uu. Tinh chat: opt[i][j-1] <= opt[i][j] <= opt[i+1][j]. Do phuc tap giam tu O(n^3) xuong O(n^2).
Step 2 / 7
Co so: dp[i][i] = 0 cho moi i. Khong co chi phi khi doan chi co 1 phan tu.
Step 3 / 7
Doan dai 2: chi co 1 diem chia, opt[i][i+1] = i. Tinh truc tiep.
Step 4 / 7
dp[0][2]: Nho Knuth, chi xet opt[0][1]..opt[1][2] = 0..1. Diem chia toi uu = 0. Chi phi = 11.
Step 5 / 7
Doan dai 3: moi o chi xet vung opt thu hep. Diem chia di chuyen don dieu sang phai tren NumberLine.
Step 6 / 7
Doan dai 4: tinh chat don dieu giup moi o chi xet O(1) diem chia trung binh. Tong = O(n^2).
Step 7 / 7
dp[0][6] = 48. Toi uu Knuth giam tu 216 phep tinh (n^3) xuong 36 (n^2). Hieu qua gap 6 lan!