DP JAVA O(n^3) Solution With Explanation, 15ms, 17 lines


  • 6

    Think about this question for three days, read the hint, still had no thought, but minimax did help, finally got this O(n^3) DP solution. Thanks @yygy for correcting me.

    Just use an example here for explaining how to find this approach.
    Suppose n is 5, draw a tree to find the minimum cost in worst cases.
    0_1469332171930_IMG_3175.JPG

    Through the tree, find the transition function:

    • f(i,j) stands for the minimum lost between guessing i and j.
    • f(i,0) = 0, f(i,i) = 0
    • f(i, i) = 0
    • f(i,i+1) = i
    • f(i,j) = min[( k from i to j) max(k+f(i,k-1), k+f(k+1,j)]
    • the answer for this problem is f(1,n)

    Then find a way to calculate the final answer. Draw a square matrix, the value will be filled in like this:
    0_1469332203192_FullSizeRender.jpg
    Here is the code:

        public int getMoneyAmount(int n) {
            int[][] f = new int[n+2][n+2];
            for(int i = 1; i <  n; i++) f[i][i+1] = i;
            for(int k = 1; k <= n-2; k++){
                for(int left = n-k-1, right = n; right >= k+2; left--,right--)
                {        
                    int min = Integer.MAX_VALUE;
                	for(int i = left; i <= right; i++){
                		int max = Math.max(i+f[left][i-1], i+f[i+1][right]);
                		if(max < min) min = max;
                	}
                	f[left][right] = min;
                }
            }
            return f[1][n];
        }
    

  • 0
    Y

    @boyzhirui Why not O(n^3)?


  • 0
    Y

    @boyzhirui When n=1000,it runs very slow, it's indeed O(n^3). This is a typical interval DP whose time complexity is general O(n^3).


  • 0

    @yygy Yeah. I am sorry. You're right. Previously I thought the solution is O(n^3), but I changed the title after I woke up.

    Since we need to fill in n^2 elements and each one will cost O(n), this solution should be O(n^3).

    There may be a better way to solve the problem.


  • 0
    D

    @ZebraRabbit Nice drawing


Log in to reply
 

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