C++刷leetcode（97. 交错字符串）【动态规划】

糖逗

题目描述:

1. 给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
   
2. 
   
3.  
   
4. 
   
5. 示例 1：
   
6. 
   
7. 输入：matrix =
   
8. [
   
9.   [0,1,1,1],
   
10.   [1,1,1,1],
    
11.   [0,1,1,1]
    
12. ]
    
13. 输出：15
    
14. 解释：
    
15. 边长为 1 的正方形有 10 个。
    
16. 边长为 2 的正方形有 4 个。
    
17. 边长为 3 的正方形有 1 个。
    
18. 正方形的总数 = 10 + 4 + 1 = 15.
    
19. 示例 2：
    
20. 
    
21. 输入：matrix =
    
22. [
    
23.   [1,0,1],
    
24.   [1,1,0],
    
25.   [1,1,0]
    
26. ]
    
27. 输出：7
    
28. 解释：
    
29. 边长为 1 的正方形有 6 个。
    
30. 边长为 2 的正方形有 1 个。
    
31. 正方形的总数 = 6 + 1 = 7.
    
32.  
    
33. 
    
34. 提示：
    
35. 
    
36. 1 <= arr.length&#160;<= 300
    
37. 1 <= arr[0].length&#160;<= 300
    
38. 0 <= arr[i][j] <= 1
    
39. 
    
40. 来源：力扣（LeetCode）
    
41. 链接：https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones
    
42. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     //dp[i][j]表示s1前i个元素和s2前j个元素能够构成加错字符s3的前i+j个元素
   
4.     bool isInterleave(string s1, string s2, string s3) {
   
5.         int len1 = s1.size(), len2 = s2.size(), len3 = s3.size();
   
6.         if (len1+len2 != len3) return false;
   
7.         vector<vector<bool>> dp(len1+1, vector<bool>(len2+1));
   
8.         dp[0][0] = true;
   
9.         for (int i = 0; i <= s1.size(); ++i) {
   
10.             for (int j = 0; j <= s2.size(); ++j) {
    
11.                 if (i == 0 && j == 0) continue;
    
12.                 bool temp1 = false, temp2 = false;
    
13.                 if (j != 0) temp1 = (s2[j-1] == s3[i+j-1] && dp[i][j-1]);
    
14.                 if (i != 0) temp2 = (s1[i-1] == s3[i+j-1] && dp[i-1][j]);
    
15.                 dp[i][j] = temp1 || temp2;
    
16.             }
    
17.         }
    
18.         return dp[len1][len2];
    
19.     }
    
20. };

复制代码

参考链接：https://leetcode-cn.com/problems ... c-dp-by-yuexiwen-4/

注意事项：1.dp[j]表示s1前i个元素和s2前j个元素能够构成加错字符s3的前i+j个元素, vector<vector<bool>> dp(len1+1, vector<bool>(len2+1));