8 lines java solution


  • 0
    F

    I use some extra space to prevent ArrayOutOfBounds, the problem is very similar to Burst Balloons, and the Matrix Chain Multiplication problem described in Introduction to Algorithms, 3 edition

        public int getMoneyAmount(int n) {
            int[][] dp = new int[n + 2][n + 2];
            for (int l = 1; l < n; l++)
                for (int i = 1; i <= n - l; i++) {
                    int j = i + l;
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = i; k <= j; k++)
                        dp[i][j] = Math.min(dp[i][j], k + Math.max(dp[i][k - 1], dp[k + 1][j]));
                }
            return dp[1][n];
        }

Log in to reply
 

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