Editorial for Quy hoạch động cổ điển

Gọi $dp[i][j]$ ~dp[i][j]~ là tổng các $f(l,r)$ ~f(l,r)~ với $l \le r \le i$ ~l \le r \le i~, trong đó $f(l,r)$ ~f(l,r)~ là số lượng cách chọn các phần tử dãy $A$ ~A~ sao cho tổng bằng $j$ ~j~.

Ta có thể biến đổi biểu thức cần tính như sau:

$\displaystyle \sum_{l=1}^{N}\sum_{r=l}^{N} f(l,r)=\sum_{l=1}^{N-1}\sum_{r=l}^{N-1} f(l,r)+\sum_{l=1}^{N}f(l,N)$

Từ đó, ta có công thức QHĐ như sau:

$dp[i][0]=i+1$ ~dp[i][0]=i+1~ với mọi $1 \le i \le N$ ~1 \le i \le N~
$dp[i][j] = dp[i-1][j] + dp[i-1][j-A_i]$ với mọi $1 \le i \le N$ ~1 \le i \le N~, $1 \le j \le S$ ~1 \le j \le S~

Độ phức tạp: $O(N.S)$ ~O(N.S)~

Editorial for Quy hoạch động cổ điển

Quy hoạch động cổ điển

Comments