目錄

1444. 切披薩的方案數(shù)

題目描述：

實(shí)現(xiàn)代碼與解析：

二維后綴和? + 動(dòng)態(tài)規(guī)劃

原理思路：

1444. 切披薩的方案數(shù)

題目描述：

????????給你一個(gè)?rows x cols?大小的矩形披薩和一個(gè)整數(shù)?k?，矩形包含兩種字符：?'A'?（表示蘋果）和?'.'?（表示空白格子）。你需要切披薩?k-1?次，得到?k?塊披薩并送給別人。

切披薩的每一刀，先要選擇是向垂直還是水平方向切，再在矩形的邊界上選一個(gè)切的位置，將披薩一分為二。如果垂直地切披薩，那么需要把左邊的部分送給一個(gè)人，如果水平地切，那么需要把上面的部分送給一個(gè)人。在切完最后一刀后，需要把剩下來的一塊送給最后一個(gè)人。

請你返回確保每一塊披薩包含?至少?一個(gè)蘋果的切披薩方案數(shù)。由于答案可能是個(gè)很大的數(shù)字，請你返回它對 10^9 + 7 取余的結(jié)果。

示例 1：

輸入：pizza = ["A..","AAA","..."], k = 3
輸出：3 
解釋：上圖展示了三種切披薩的方案。注意每一塊披薩都至少包含一個(gè)蘋果。

示例 2：

輸入：pizza = ["A..","AA.","..."], k = 3
輸出：1

示例 3：

輸入：pizza = ["A..","A..","..."], k = 1
輸出：1

提示：

• 1 <= rows, cols <= 50
• rows ==?pizza.length
• cols ==?pizza[i].length
• 1 <= k <= 10
• pizza?只包含字符?'A'?和?'.'?。

實(shí)現(xiàn)代碼與解析：

二維后綴和? + 動(dòng)態(tài)規(guī)劃

class Solution {
public:
    int ways(vector<string>& pizza, int k) {

        int m = pizza.size(), n = pizza[0].size(), mod = 1e9 + 7;
        vector<vector<vector<int>>> f(k, vector<vector<int>>(m, vector<int>(n)));

        vector<vector<int>> apples(m + 1, vector<int>(n + 1)); // 后綴和

        // 后綴和 與 初始化dp數(shù)組
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = n - 1; j >= 0; j--)
            {
                apples[i][j] = apples[i + 1][j] + apples[i][j + 1] - apples[i + 1][j + 1] + (pizza[i][j] == 'A');
                f[0][i][j] = apples[i][j] > 0;
            }
        } 

        for (int kk = 1; kk < k; kk++)
        {
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    // 選擇此刀的切割位置

                    // 水平切, 遍歷切的位置
                    for (int a = i + 1; a < m; a++)
                    {
                        // 上面的一塊中至少要有一個(gè)蘋果
                        if (apples[i][j] > apples[a][j])
                        {
                            f[kk][i][j] = (f[kk][i][j] + f[kk - 1][a][j]) % mod;
                        }
                    }
                
                    // 垂直切
                    for (int b = j + 1; b < n; b++)
                    {
                        // 左側(cè)塊中至少有一個(gè)蘋果
                        if (apples[i][j] > apples[i][b])
                        {
                            f[kk][i][j] = (f[kk][i][j] + f[kk - 1][i][b]) % mod;
                        }
                    }
                }
            }
        }
        
        return f[k - 1][0][0];
    }
};

原理思路：

? ? ? ? apples 數(shù)組，后綴和用于記錄一塊披薩中的蘋果數(shù)量，用一塊中的左上角來代替此塊含有的蘋果數(shù)。

? ? ? ? 此題的關(guān)鍵是，dp[ k ][ i ][ j ] 的含義：代表還剩下 k 刀沒切，剩下的是左上角為?i ，j 的披薩狀態(tài)時(shí)的切割方案總數(shù)。這是我自己的理解，力扣上dp數(shù)組定義的含義感覺不如我這樣寫和解釋更直觀，不過原理肯定是一樣的。

? ? ? ? 知道dp數(shù)組的含義，就很好寫了。

? ? ? ? 首先計(jì)算 apples 數(shù)組，這個(gè)就不用解釋了，不會(huì)的話，建議去學(xué)習(xí)一下前綴和，二維前綴和的基礎(chǔ)算法就行，同時(shí)初始化一下dp。

? ? ? ? 初始化dp數(shù)組：顯然在還需要切0刀，剩下最后一塊披薩中有蘋果時(shí)，表示切好了，是一種情況，賦值為1，否則不成立賦值為0；

f[0][i][j] = apples[i][j] > 0;

? ? ? ? 遍歷順序：一定是先遍歷切割刀數(shù)，因?yàn)榫捅热缫粋€(gè)形狀披薩狀態(tài)下，切兩刀肯定需要切一刀的狀態(tài)遞推而來，后面根據(jù)遞推式也能看出來。

? ? ? ? 遞推方程：兩種切法分類討論：

? ? ? ? 水平切：肯定是從第一行下邊開始切，總不能切空氣吧，所以是 i + 1 開始遍歷，然后切完后上面的那塊中一定要有蘋果，所以需要判斷一下，切完此刀后，剩下的大塊需要再切 kk - 1刀，我們就不用再去遍歷了，dp數(shù)組含義就是這個(gè)，根據(jù)這個(gè)寫出遞推式。

????????????????遞推式：f[ kk ][ i ][ j ] = (f[ kk ][ i ][ j ] + f[ kk - 1 ][ a ][ j ]) % mod;

? ? ? ? 垂直切：與水平切同理，直接給出遞推式：

? ? ? ? ? ? ? ? 遞推式：f[ kk ][ i ][ j ] = (f[ kk ][ i ][ j ] + f[ kk - 1 ][ i ][ b ]) % mod;

? ? ? ?最后，返回結(jié)果，顯然，在初始狀態(tài)還剩切k - 1刀時(shí)是我們需要的結(jié)果狀態(tài)。

???????return f[ k - 1 ][ 0 ][ 0 ];

???????結(jié)束。文章來源地址http://www.zghlxwxcb.cn/news/detail-657081.html

到了這里，關(guān)于Leetcode每日一題：1444. 切披薩的方案數(shù)（2023.8.17 C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！