Interval DP

// dp[i][j] = answer for interval [i..j]
// For length l from 2 to n:
//   For all intervals [i, j] of length l:
//     Try all split points k: dp[i][j] = f(dp[i][k], dp[k+1][j], ...);

for (int len = 2; len <= n; len++) {
    for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;
        dp[i][j] = Integer.MAX_VALUE; // or MIN_VALUE depending on problem
        for (int k = i; k < j; k++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, k, j));
        }
    }
}

// Burst all balloons for maximum coins
// nums[i] * nums[i-1] * nums[i+1] coins when bursting i
// Key insight: think of k as the LAST balloon to burst in [i..j]
public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] balls = new int[n + 2];
    balls[0] = balls[n+1] = 1;
    for (int i = 0; i < n; i++) balls[i+1] = nums[i];
    int N = n + 2;
    int[][] dp = new int[N][N];
    // dp[i][j] = max coins from bursting all balloons strictly between i and j
    for (int len = 2; len < N; len++) {
        for (int left = 0; left < N - len; left++) {
            int right = left + len;
            for (int k = left + 1; k < right; k++) {
                dp[left][right] = Math.max(dp[left][right],
                    dp[left][k] + balls[left] * balls[k] * balls[right] + dp[k][right]);
            }
        }
    }
    return dp[0][N-1];
}

// Minimum operations to multiply a chain of matrices
public int matrixChainOrder(int[] dims) {
    int n = dims.length - 1; // number of matrices
    int[][] dp = new int[n][n];
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j]
                         + dims[i] * dims[k+1] * dims[j+1];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n-1];
}

// LeetCode 1547
public int minCost(int n, int[] cuts) {
    Arrays.sort(cuts);
    int m = cuts.length;
    int[] c = new int[m + 2];
    c[0] = 0; c[m+1] = n;
    for (int i = 1; i <= m; i++) c[i] = cuts[i-1];
    int[][] dp = new int[m+2][m+2];
    for (int len = 2; len < m+2; len++) {
        for (int i = 0; i < m+2-len; i++) {
            int j = i + len;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i+1; k < j; k++)
                dp[i][j] = Math.min(dp[i][j],
                    dp[i][k] + dp[k][j] + c[j] - c[i]);
        }
    }
    return dp[0][m+1];
}