切披萨的方案数

/*
 * Problem: You are given a rectangular pizza represented as a matrix of characters 'A' (apple) and '.' (empty cell). You need to cut the pizza k-1 times into k pieces such that each piece contains at least one apple.
 * Approach using Java Streams:
 * 1. Similar to the standard approach but leverages Java Streams for concise code.
 * 2. Use a prefix sum array to calculate the number of apples in each sub-pizza.
 * 3. Implement dynamic programming using streams to accumulate the number of ways to cut the pizza.
 * 4. The dp array will store the number of ways to cut the sub-pizza starting from a given cell with a specific number of cuts left.
 */
import java.util.*;
import java.util.stream.IntStream;

public class WaysToCutPizzaStream {
    private static final int MOD = 1_000_000_007;

    public int waysToCutPizza(String[] pizza, int k) {
        int rows = pizza.length, cols = pizza[0].length();
        int[][][] dp = new int[rows + 1][cols + 1][k + 1];
        int[][] prefixSum = new int[rows + 1][cols + 1];

        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                prefixSum[i][j] = (pizza[i].charAt(j) == 'A' ? 1 : 0) + prefixSum[i + 1][j] + prefixSum[i][j + 1] - prefixSum[i + 1][j + 1];
                dp[i][j][1] = prefixSum[i][j] > 0 ? 1 : 0;
            }
        }

        for (int cuts = 2; cuts <= k; cuts++) {
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    int finalI = i;
                    int finalJ = j;
                    dp[i][j][cuts] = (IntStream.range(i + 1, rows).filter(row -> prefixSum[finalI][finalJ] - prefixSum[row][finalJ] > 0).map(row -> dp[row][finalJ][cuts - 1]).sum() % MOD
                            + IntStream.range(j + 1, cols).filter(col -> prefixSum[finalI][finalJ] - prefixSum[finalI][col] > 0).map(col -> dp[finalI][col][cuts - 1]).sum() % MOD) % MOD;
                }
            }
        }
        return dp[0][0][k];
    }
}