戳气球

/*
 * 思路：
 * 1. 使用动态规划的方式解决该问题，但是使用Java Stream来进行数据的处理。
 * 2. 依旧是使用 dp 数组来存储每个区间内的最大硬币数。
 * 3. 通过Stream API进行数据流式处理，代码会更加简洁和直观。
 */
import java.util.Arrays;
 
public class BurstBalloonsStream {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] newNums = new int[n + 2];
        newNums[0] = 1;
        newNums[n + 1] = 1;
        System.arraycopy(nums, 0, newNums, 1, n);
 
        int[][] dp = new int[n + 2][n + 2];
        Arrays.stream(dp).forEach(row -> Arrays.fill(row, 0));
 
        for (int length = 1; length <= n; length++) {
            for (int left = 1; left <= n - length + 1; left++) {
                int right = left + length - 1;
                int l = left, r = right;
                dp[left][right] = Arrays.stream(newNums, left, right + 1)
                    .map(k -> dp[left][k - 1] + newNums[left - 1] * k * newNums[right + 1] + dp[k + 1][right])
                    .max()
                    .orElse(0);
            }
        }
        return dp[1][n];
    }
}