合并石头的最低成本

/*
 * 思路：
 * 使用Java Stream API实现相同的动态规划解决方案。
 * 1. 使用流来初始化前缀和数组。
 * 2. 在DP部分依旧采用嵌套循环实现。
 */

import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {
    public int mergeStones(int[] stones, int K) {
        int n = stones.length;
        if ((n - 1) % (K - 1) != 0) return -1;
        int[][] dp = new int[n][n];
        int[] prefixSum = new int[n + 1];
        IntStream.range(0, n).forEach(i -> prefixSum[i + 1] = prefixSum[i] + stones[i]);
        IntStream.rangeClosed(K, n).forEach(len ->
            IntStream.rangeClosed(0, n - len).forEach(i -> {
                int j = i + len - 1;
                dp[i][j] = IntStream.iterate(i, m -> m < j, m -> m + K - 1)
                                     .map(m -> dp[i][m] + dp[m + 1][j])
                                     .min().orElse(Integer.MAX_VALUE);
                if ((j - i) % (K - 1) == 0) dp[i][j] += prefixSum[j + 1] - prefixSum[i];
            })
        );
        return dp[0][n - 1];
    }
}