Nhận xét: giá trị kì vọng của hàm call(a, b) và call(c, d) sẽ bằng nhau nếu ~b - a = d - c~.

Gọi ~f[i]~ là giá trị kì vọng của hàm call(l, r) với ~r - l + 1 = i~. Ta có công thức quy hoạch động sau:

~f[i] = (1 + f[i]) + \sum \limits_{j = 1}^{i - 2} (1 + f[j] + f[i - j - 1]) + (1 + f[i])~

~\Rightarrow f[i] = i + 2 \cdot f[i] + \sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])~

~\Rightarrow (i - 2) \cdot f[i] = i + \sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])~

~\Rightarrow f[i] = \dfrac{i + \sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])}{i - 2}~

Để tính nhanh ~\sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])~, ta có thể sử dụng prefix sum (tổng tiền tố).

Độ phức tạp: ~O(n)~.