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

  • 0

    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.

Log in to reply

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