java O(n^3) solution w/ easy to understand proof

• Here is a solution inspired by awice's python solution with a proof that is hopefully easy to understand.

``````int dp(int i, int j){
if(i > j) return 0;
if(i == j) return 1;
if(mem[i][j] == -1){ //result is not memoized yet
if(a[i] == a[j]){
mem[i][j] = dp(i, j-1);
} else {
int ans = j-i+1;
for(int k=i; k<=j; k++)
if(a[k] == a[i])
ans = Math.min(ans, dp(i,k) + dp(k+1, j));
mem[i][j] = ans;
}
}
return mem[i][j];
}
``````

algorithm idea:
• do recursion and memoization.
• dp[i][j] = min #prints to solve for range i to j inclusive.
• base cases
i > j -> 0
i == j -> 1
• recursive cases
a[i] == a[j] -> dp[i][j-1]
a[i] != a[j] -> min(dp[i][k] + dp[k+1][j]) for all k where i<=k<=j && a[i] == a[k]

• proof of     a[i] == a[j] -> dp[i][j-1]:
An optimal schedule exists where we first print a[i] onto the entire range [i,j].
This is because it is always fine to print a[i] onto cell i first, but we might as well extend this print onto all other cells, since it might be more useful for those cells to start out with a[i] instead of a blank value.
Therefore, it is fine to assume that we always first print a[i] onto the entire range [i,j].

Because we can make this assumption, solve range [i,j] costs same as problem range[i,j-1], since satisfying cell j takes no additional prints.

• proof of     a[i] != a[j] -> min(dp[i][k] + dp[k+1][j]) for all k where i<=k<=j && a[i] == a[k]:
Lets pivot on the rightmost character of the first print that did not get overwritten.
Denote the index of this character as k.

Obviously, if cell k did not get overwritten, then a[k] == a[i]

For given k, the structure of the schedule is to first print on the entire range [i,j], and then finish satisfying all constraints without printing on or across cell k.
Note that the first print can also be on the range [i,k], since any character printed right of cell k will be overwritten (by definition).
Therefore, the structure of this schedule is the same as solving range[i,k] and range[k+1,j] separately.

Trying all candidate indexes k, and finding the minimum #prints given certain k, will lead us to the optimal answer.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.