C++刷LeetCode（1444. 切披萨的方案数）【动态规划】

糖逗

题目描述：

1. 给你一个 rows x cols 大小的矩形披萨和一个整数 k ，矩形包含两种字符： 'A' （表示苹果）和 '.' （表示空白格子）。你需要切披萨 k-1 次，得到 k 块披萨并送给别人。
   
2. 
   
3. 切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。
   
4. 
   
5. 请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。
   
6. 
   
7.  
   
8. 
   
9. 示例 1：
   
10. 
    
11. 
    
12. 
    
13. 输入：pizza = ["A..","AAA","..."], k = 3
    
14. 输出：3
    
15. 解释：上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。
    
16. 示例 2：
    
17. 
    
18. 输入：pizza = ["A..","AA.","..."], k = 3
    
19. 输出：1
    
20. 示例 3：
    
21. 
    
22. 输入：pizza = ["A..","A..","..."], k = 1
    
23. 输出：1
    
24.  
    
25. 
    
26. 提示：
    
27. 
    
28. 1 <= rows, cols <= 50
    
29. rows ==&#160;pizza.length
    
30. cols ==&#160;pizza[i].length
    
31. 1 <= k <= 10
    
32. pizza&#160;只包含字符&#160;'A'&#160;和&#160;'.'&#160;。
    
33. 
    
34. 来源：力扣（LeetCode）
    
35. 链接：https://leetcode-cn.com/problems/number-of-ways-of-cutting-a-pizza
    
36. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. private:
   
3.     int mode = 1e9+7;
   
4.     vector<vector<int> >number;
   
5. public:
   
6.     //计算以i, j为左上角顶点;m,n为右下角顶点的矩形中是否有A
   
7.     bool Has_A(int i, int j, int m, int n){
   
8.         int temp1 = 0, temp2 = 0, temp3 = 0;
   
9.         if(i-1 >= 0)temp1 = number[i-1][n];
   
10.         if(j-1 >= 0)temp2 = number[m][j-1];
    
11.         if(i-1 >= 0 && j-1 >= 0)temp3 = number[i-1][j-1];
    
12.         return number[m][n] - (temp1 + temp2 - temp3) > 0;
    
13.     }
    
14.     int ways(vector<string>& pizza, int k) {
    
15.         int len1 = pizza.size(), len2 = pizza[0].size();
    
16.         //number[i][j]记录以(i,j)为底的pizza中有多少个苹果
    
17.         number = vector<vector<int> >(len1, vector<int>(len2, 0));
    
18.         if(pizza[0][0] == 'A')number[0][0] = 1;
    
19.         for(int i = 1; i < len1; i++){
    
20.             number[i][0] = number[i-1][0] + (pizza[i][0] == 'A');
    
21.         }
    
22.         for(int j = 1; j < len2; j++){
    
23.             number[0][j] = number[0][j-1] + (pizza[0][j] == 'A');
    
24.         }
    
25.         for(int i = 1; i < len1; i++){
    
26.             for(int j = 1; j < len2; j++){
    
27.                 number[i][j] = number[i-1][j] + number[i][j-1] - number[i-1][j-1] + (pizza[i][j] == 'A');
    
28.             }
    
29.         }
    
30.         //dp[i][j][k]i,j表示披萨剩余部分的左上角,k表示当前披萨被切成k块
    
31.         vector<vector<vector<int> > >dp(len1, vector<vector<int> >(len2, vector<int>(k+1, 0)));
    
32.         //初始化
    
33.         dp[0][0][1] = 1;
    
34.         for(int m = 2; m <= k; m++){
    
35.             for(int i = 0; i < len1; i++){
    
36.                 for(int j = 0; j < len2; j++){
    
37.                     if(dp[i][j][m-1] == 0)continue;
    
38.                     //穷举水平切
    
39.                     for(int z = i+1; z < len1; z++){
    
40.                         if(Has_A(i, j, z-1, len2-1) && Has_A(z, j, len1-1, len2-1)){
    
41.                             dp[z][j][m] += dp[i][j][m-1];
    
42.                             dp[z][j][m] %= mode;
    
43.                         }
    
44.                     }
    
45.                     //穷举垂直切
    
46.                     for(int z = j + 1; z < len2; z++){
    
47.                         if(Has_A(i, j, len1-1, z - 1) && Has_A(i, z, len1-1, len2-1)){
    
48.                             dp[i][z][m] += dp[i][j][m-1];
    
49.                             dp[i][z][m] %= mode;
    
50.                         }
    
51.                     }
    
52.                 }
    
53.             }
    
54.         }
    
55.         long long res = 0;
    
56.         for(int i = 0; i < len1; i++){
    
57.             for(int j = 0; j < len2; j++){
    
58.                 res += dp[i][j][k];
    
59.             }
    
60.             res %= mode;
    
61.         }
    
62.         return res;
    
63.     }
    
64. };

复制代码

参考链接：https://leetcode-cn.com/problems ... i-hua-c-by-smilyt_/