切披萨的方案数

929code / 2023-08-17 / 原文

给你一个 rows x cols 大小的矩形披萨和一个整数 k ，矩形包含两种字符： 'A' （表示苹果）和 '.' （表示空白格子）。
你需要切披萨 k-1 次，得到 k 块披萨并送给别人。
切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。
如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。
在切完最后一刀后，需要把剩下来的一块送给最后一个人。
请你返回确保每一块披萨包含至少一个苹果的切披萨方案数。

1. 记忆化搜索

class Solution {
public:
    const int MOD = 1e9 + 7;
    int ways(vector<string>& pizza, int k) {
        //求方案数目,一共有k-1刀的机会
        //可以选择横刀和竖刀
        //分别有m-2和n-2个落刀位置
        //切到相同状态时，剩下的方案数相同的，这里可以考虑使用记忆化搜索
        int m = pizza.size();
        int n = pizza[0].size();
        int res = 0;
        int dp[m*n][k];
        memset(dp,0,sizeof(dp)); 
        function<int(int,int)> f = [&](int state, int times)->int{
            int x = state/n; int y = state%n;
        };
        return f(0,0);//初始状态为0,切了0刀
    }
};