Các bạn cho mình hỏi cách làm bài này bằng quy hoạch động:
Cho một dãy n số, hãy tìm cách chia dãy thành các đoạn con sao cho mỗi đoạn có tổng không lớn hơn M và tổng chênh lệch tổng của các đoạn là nhỏ nhất.
Có
N <= 2000
M <= 1000000
Input: dòng đầu cho 2 số M, N
Dòng 2 là n số của dãy
Output: in ra kết quả duy nhất là tổng chênh lệch nhỏ nhất tìm được
Test đề bài:
In:
6 4
4 3 2 5
Out:
3