鏈接：

1444. 切披薩的方案數

題意：

給定一個矩陣，其中含有多個蘋果，需要切割k-1次,每次可以切割多行/多列，需要保證切割兩個部分都有蘋果，移除靠上/靠右的部分，對留下部分進行后續的切割，求有幾種切割方法

解：

男人不能快算法需要快！

這題需要通過兩部分節約時間，一部分是動態規劃，一部分是前綴和

這好像還是第一次寫二維前綴和（好像），主要是要記得移除重復部分，由于每次保留的是靠下/靠左的部分，所以求的是已i j 為起點的右下角和

動態規劃部分，我們需要一個三維的DP[k][i][j]，分別代表從i j開始的右下角矩陣，成功切割k-1刀的方案數量

初始值是DP[1][i][j]=(sum[i][j] > 0)，即這一整塊上存在蘋果

遞推公式需要判斷行切和列切，判斷條件非常巧妙，是整體蘋果數量 > 切割后剩下的蘋果數量，公式是整體+=切割后的部分

整體DP[temp][i][j]，假設在i2位置進行切割，則判斷sum[i][j] > sum[i2][j]，若為真即計算DP[temp][i][j]+=DP[temp-1][i2][j]，要注意切割后所需的切割數-1

實際代碼：

#include<bits/stdc++.h>
using namespace std;
constexpr static int Mod=1E9+7; 
int ways(vector<string>& pizza, int k)
{int lgrow=pizza.size(),lgcol=pizza[0].length();vector<vector<int>>sum(lgrow+1,vector<int>(lgcol+1));vector<vector<vector<int>>>dp(k+1,vector<vector<int>>(lgrow+1,vector<int>(lgcol+1)));//初始化 for(int i=lgrow-1;i>=0;i--){for(int j=lgcol-1;j>=0;j--){sum[i][j]=sum[i+1][j]+sum[i][j+1]-sum[i+1][j+1]+(pizza[i][j]=='A');//二維前綴和 矩陣計算 dp[1][i][j]=sum[i][j]>0;}}//dp遞推 for(int dp_k=2;dp_k<=k;dp_k++){for(int i=lgrow-1;i>=0;i--){for(int j=lgcol-1;j>=0;j--){//行切割for(int i2=lgrow-1;i2>i;i2--){if(sum[i][j]>sum[i2][j])//切出來的有蘋果{dp[dp_k][i][j]+=dp[dp_k-1][i2][j];dp[dp_k][i][j]%=Mod;}}//列切割for(int j2=lgcol-1;j2>j;j2--){if(sum[i][j]>sum[i][j2])//切出來的有蘋果{dp[dp_k][i][j]+=dp[dp_k-1][i][j2];dp[dp_k][i][j]%=Mod;}}}}}return dp[k][0][0];
}
int main()
{int k;cin>>k;vector<string> pizza;string s;while(cin>>s) pizza.push_back(s);int ans=ways(pizza,k);cout<<ans<<endl;return 0;
}

限制：

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