Here is another way to optimize some 1D1D dynamic programming problem that I know.

Suppose that the old choice will only be worse compare to the new choice(it is quite common in such kind of problems).

Then suppose at current time we are deal with dp_i, and we have some choice a₀ < a₁ < a₂, ..., a_k - 1 < a_k. then we know at current time a_i should be better than a_i + 1. Otherwise it will never be better than a_i + 1,so it is useless.

we can use a deque to store all the a_i.

And Also Let us denote D(a, b) as the smallest i such that choice b will be better than a.

If D(a_i, a_i + 1) > D(a_i + 1, a_i + 2),we can find a_i + 1 is also useless because when it overpass a_i,it is already overpass by a_i + 2.

So we also let D(a_i, a_i + 1) < D(a_i + 1, a_i + 2). then we can find the overpass will only happen at the front of the deque.

So we can maintain this deque quickly, and if we can solve D(a, b) in O(1),it can run in O(n).

For question 2: The sufficient condition is: C[a][d] + C[b][c] ≥ C[a][c] + C[b][d] where a < b < c < d.

There is one more optimization of dimanic progamming: 101E - Candies and Stones (editoral)

you have put problem "B. Cats Transport" in "Convex Hull Optimization1", actually it belongs to "Convex Hull Optimization2"

For this moment it's the most useful topic of this year. Exactly in the middle: June 30th, 2013.

this one seemed a nice dp with optimization to me:https://www.hackerrank.com/contests/monthly/challenges/alien-languages

The problem mentioned in the article (Breaking Strings) is "Optimal Binary Search Tree Problem" , traditional one.

It can be solved by simple DP in O(N^3), by using Knuth's optimization , in O(N^2) . But it still can be solved in O(NlogN) — http://poj.org/problem?id=1738 (same problem but bigger testcases) (I don't know how to solve it. I hear the algorithm uses meld-able heap)

Convex Hull Optimization 1 Problems:

• APIO 2010 task Commando

• TRAKA

• ACQUIRE

• SkyScrapers (+Data Structures)

Convex Hull Optimization 2 Problems:

• BAABO

Convex Hull Optimization 3 Problems (No conditions for a[] array and b[] array) :

• GOODG

• BOI 2012 Day 2 Balls

• Cow School

• Solution-Video

For some reason I cannot open the links with firefox because they go over the Top Rated table.

One more problem where Knuth Optimization is used:
Andrew Stankevich Contest 10, Problem C.
BTW, does anybody know how to insert a direct link to a problem from gyms?

I need some problems to solve on Divide and Conquer Optimization. Where can I find them? An online judge / testdata available would be helpful.

can anyone provide me good editorial for dp with bitmask .

Has matrix-exponent optimizations been included here?

Can matrix chain multiplication problem b also optimized by knuth optimization? If not, dn why?

What are some recent USACO questions that use this technique or variations of it?

Can this problem be solved using convex hull optimization?

You are given a sequence A of N positive integers. Let’s define “value of a splitting” the sequence to K blocks as a sum of maximums in each of K blocks. For given K find the minimal possible value of splittings.

N <= 10⁵

K <= 100

Input:       Output: 
5 2          6
1 2 3 4 5    

Could you elaborate a little me more in the "Convex Hull Optimization2" and other sections for the clearer notations.

For example, You have "k" — a constant in O(kn^2). So the first dimension is of the length K and the second dimension is of the length N?

I think it would be clearer if you can write dp[n], dp[k][n] ... instead of dp[i], dp[i][j] .

Best regards,

I don't get it why there is a O(logN) depth of recursion in Divide and conquer optimization ?
Can someone explain it ?

Hello , I have a doubt can anyone help?

In the divide and conquer optimization ,can we always say that it is possible to use in a system where we have to minimize the sum of cost of k continuous segments( such that their union is the whole array and their intersection is null set) such that the cost of segment increases with increase in length of the segment?

I feel so we can and we can prove it using contradiction Thanks :)

For convex hull optimizations, with only b[j] ≥ b[j + 1] but WITHOUT a[i] ≤ a[i + 1],

I don't think the complexity can be improved to O(n), but only O(n log n) Is there any example that can show I am wrong?

ZOJ is currently dead. For the problem "Breaking String" (Knuth opt.), please find at here

please someone tell me why in convex hull optimization should be b[j] ≥ b[j + 1] and a[i] ≤ a[i + 1]
in APIO'10 Commando the DP equation is
Dp[i] = -2 * a * pre_sum[j] * pre_sum[i] + pre_sum[j]^2 + Dp[j] -b * pre_sum[j] + a * pre_sum[i]^2 + b * pre_sum[i] + c
we can use convex hull trick so the line is y = A * X + B
A = -2 * a * pre_sum[j]
X = pre_sum[i]
B = pre_sum[j]^2 + Dp[j] -b * pre_sum[j]
Z = a * pre_sum[i]^2 + b * pre_sum[i] + c
and then we can add to Dp[i] += Z , because z has no relation with j
the question is , since a is always negative (according to the problem statement) and pre_sum[i],pre_sum[j] is always increasing we conclude that b[j] ≤  b[j + 1] and a[i] ≤ a[i + 1]
I've coded it with convex hull trick and got AC , and the official solution is using convex hull trick
someone please explain to me why I'm wrong or why that is happening
thanks in advance

Is it necessary for the recurrence relation to be of the specific form in the table for Knuth's optimization to be applicable? For example, take this problem. The editorial mentions Knuth Optimization as a solution but the recurrence is not of the form in the table. Rather, it is similar to the Divide-and-Conquer one, i.e. dp[i][j] = mink < j{dp[i - 1][k] + C[k][j]}. Does anyone know how/why Knuth's optimization is applicable here?

It is also worthwhile to mention the DP Optimization given here http://mirror.codeforces.com/blog/entry/49691 in this post.

Can we have the same dp optimizations with dp[i][j] = max (dp....)?

can someone please give me intuition on proof of A[i, j - 1] ≤ A[i, j] ≤ A[i + 1, j] given for knuth optimization of optimal binary search tree.

Fresh problem. Can be solved with CHT.

What will be the actual complexity of Knuth optimization on a O(n^2 * k) DP solution ? Will it be O(n^2) or O(n*k)? Here n = number of elements and k = number of partitions.

Someone know where i can find an article about Lagrange optimization? (i know that this can be used for reduce one state of the dp performing a binary search on a constant and add this on every transition until the realized number of transition for reach the final state become the desired)

I know this can be treated as off-topic by many of us, but what about solving DP states which are direct arithmetic (specifically sum/difference) of previous states:

Say the DP state is 1D, like in Fibonacci series (dp[i] = dp[i-1] + dp[i-2]), we already know of a solution in O(k^3 * log n) using matrix binary exponentiation, where k represents that dp[i] depends on dp[i-1], dp[i-2], .. dp[i-k].

Is there an optimisation for 2D states like the same? Say the state is as follows:

dp[i][j] = dp[i][j-1] + dp[i-1][j-1] + dp[i-1][j-2]
dp[i][j] = 0, i < j

I am finding it hard to reduce it to any less than O(n * m) for finding dp[n][m]

https://www.youtube.com/watch?v=OrH2ah4ylv4 a video by algorithms live for convex hull trick. The link given for convex hull optimization is dead now please update.

I know it's necroposting, but still. Can anyone give a link to tutorial or something(in English) for the trick used in IOI16 Aliens problem?

Can someone help me prove that the sufficient conditions for Divide and Conquer Optimization are satisfied in this problem.
I was able to solve it using the same technique with some intuition. But wasn't able to formally prove it.

Please update link of Convex Hull Optimize1 that link is now dead.

https://web.archive.org/web/20181030143808/http://wcipeg.com/wiki/Convex_hull_trick

I solved Problem 1. Redistricting from the Platinum division of the USACO 2019 January contest in O(n) using the deque optimization described in this comment while the official solution is O(n log n).

#include <iostream>
#include <deque>
#include <cassert>
#include <fstream>
using namespace std;

constexpr int maxn = 300005;

int n, k;
bool guernsey[maxn]; //true if a pasture has a guernsey
int dp[maxn]; //min number of guernsey majority or tied districts with first i pastures, 1 indexed
int suffix[maxn]; //number of guernseys minus number of holsteins for pastures starting from i, 0 indexed

bool bad(int a, int b) //returns true is b is always at least as good as a, 1 indexed
{
	return dp[a] != dp[b] ? dp[a] > dp[b] : suffix[a] >= suffix[b];
}

int main()
{
	ifstream fin("redistricting.in");
	ofstream fout("redistricting.out");
	fin >> n >> k;
	for (int i = 0; i < n; i++) //input
	{
		char t;
		fin >> t;
		guernsey[i] = t == 'G';
	}
	for (int i = n - 1; i >= 0; i--) //compute suffixes
	{
		suffix[i] = suffix[i + 1] + (guernsey[i] ? 1 : -1);
	}
	deque<int> q; //stores the indices of potential minimum values
	q.push_back(0);
	for (int i = 1; i <= n; i++)
	{
		assert(!q.empty());
		if (i - q.front() > k) //too far away
		{
			q.pop_front();
		}
		assert(!q.empty());
		int best = q.front();
		dp[i] = dp[best] + (suffix[best] - suffix[i] >= 0);
		while (!q.empty() && bad(q.back(), i))
		{
			q.pop_back();
		}
		q.push_back(i);
	}
	fout << dp[n] << '\n';
}

orz indy256 meta-san. optimizing the optimization technique itself?

Cp-algorithms has added official translation of Divide and Conquer Optimization, thought it might be useful to add. https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html

Also exists Alien's optimization (link1, link2).

iShibly

Can anyone explain how to bring the DP of NKLEAVES to the form of Convex Hull Optimization 2 from above? More specifically, how to I define $$$b$$$ and $$$a$$$ from $$$dp[i][j] = \min\limits_{k \lt j}(dp[i - 1][k] + b[k] \cdot a[j])$$$ so that $$$b[k] \geq b[k + 1]$$$ and $$$a[j] \leq a[j + 1]$$$?

My DP so far is $$$dp[i][j] = \min\limits_{k \lt j}(dp[i - 1][k] + cost(k, j))$$$ where $$$cost(k, j)$$$ is the cost to move leaves from $$$(k+1)$$$-th to $$$j$$$-th into a pile at location $$$j$$$. After some simplification, we have:

where $$$sum(k) = \sum\limits_1^k w(i)$$$ and $$$wsum(k) = \sum\limits_1^k i \cdot w(i)$$$ which we can precompute.

If we fix $$$j$$$ then in the formula above, $$$sum[j] \cdot j - wsum[j]$$$ is a constant that we can ignore and focus on $$$-sum(k) \cdot j + wsum(k) + dp[i - 1][k]$$$ and for each $$$k$$$ define a line $$$hx + m$$$ where $$$h = -sum(k)$$$ and $$$m = wsum(k) + dp[i - 1][k]$$$. We then use CHT to get values for all $$$j$$$ on $$$i$$$-th row in $$$O(n)$$$ time.

But it still baffles me how to bring my formula to the neat one in the post.

Are there any other optimization techniques?

Sorry if I misunderstanding your questions, but here are some DP-optimization techniques

1. DP-bitmask

By storing all states by bit numbers, in most problems, you can have some bitwise tricks that reduce both constant time (calculating by bitwise cost less) and complexity ($$$O(f(x))$$$ -> $$$O(\frac{f(x)}{w})$$$, $$$w$$$ is normally use as $$$wordsize = 32$$$)

2. Space-optimization

In some problems where we only care about $$$f[n][..]$$$ and $$$f[n][..]$$$ depends on $$$f[n - 1][..]$$$ then we can reduce to $$$2$$$ DP-array $$$f[0][..]$$$ & $$$f[1][..]$$$ (reduced $$$O(n)$$$ times of space)

Some other linear reccurence $$$f[n][..]$$$ depends on $$$f[n][..], f[n - 1][..], ... f[n - k][..]$$$ and when $$$k$$$ is much smaller than $$$n$$$ we can use this trick with $$$k$$$ DP-array (reduced $$$O(\frac{n}{k})$$$ times of space)

3. Recursive-DP with branch-and-bound

Normally Iterative-DP runs faster than Recursive-DP. But in some specific case as $$$Knapsack_{\ 0/1}$$$ problem, where we can have some good observations with optimizing algorithm by remove as many not-good cases as possibles. We can have much fewer cases to take care for.

Ofcourse in some cases it will break the $$$space-optimization$$$ tricks, and we have to store data by another ways to reduce the time (like using global variables, passing reference data)

4. DP-swaplabel

Sometimes by changing DP-states will results in another way of computing the results, thus will change the complexity

** 5. Alien trick**

Can you add ioi 2016 alien's trick to the tables with the conditions required to be satisfied for the trick to be used ?

There's one more optimization idea which came in one of the recent contests as well.

Consider dp[i] as array of n points.

Now, if recurrence is as follows: dp[i] is a linear combination of different j values of dp[i-1] and where coefficients are independent of j.

example: dp[i][j] = dp[i-1][j1] + c_1(i)*dp[i-1][j2] + c_2*dp[i-1][j3]+.....

we can do this naively in O(N^2), But to optimize it, one can use FFT algorithm treating dp[i] and dp[i-1] as polynomials.

for example: consider the recurrence: dp[i][j]= 2*dp[i-1][j-1] + 3*dp[i-1][j] and we need to find dp[n][j0]

so, let A= [3 2] => a(x) = 3 + 2*x and B = vector(dp(i-1)) => b_i(x) = dp[i-1][0] + dp[i-1][1]*x + dp[i-1][2]*x^2 +....+dp[i-1][j-1]*x^(j-1) + dp[i-1][j]*x^j +....+dp[i-1][n]*x^n.

Now, to get dp[i][j] we can multiply the above polynomials to get C=A*B, and then dp[i][j] will be the coefficient of x^j. This can be done in O(N*logN) using FFT.

But doing this N times will get TC O(N*N*logN)

Now, how to optimize this?

This is one of the idea to optimize recurrence using FFT.

Problem that can be solved using this technique: Colourful Balls-codechef

This knowledge is so hard :(( , how to be fluent in it :((