leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1444.cpp (1183B)

0 class Solution { 1 int n, m, mod = 1e9 + 7; 2 vector<vector<int>> count; 3 vector<vector<vector<int>>> dp = vector(10, vector(50, vector(50, -1))); 4 5 int rec(int row, int col, int left) { 6 if (count[row][col] == 0) return 0; 7 if (left == 0) return 1; 8 if (dp[left][row][col] != -1) return dp[left][row][col]; 9 10 int &res = dp[left][row][col] = 0; 11 for (int i = row; i < n - 1; i++) { 12 if (count[row][col] - count[i + 1][col] <= 0) continue; 13 res = (res + rec(i + 1, col, left - 1)) % mod; 14 } 15 16 for (int i = col; i < m - 1; i++) { 17 if (count[row][col] - count[row][i + 1] <= 0) continue; 18 res = (res + rec(row, i + 1, left - 1)) % mod; 19 } 20 21 return res; 22 } 23 24 public: 25 int ways(vector<string> &pizza, int k) { 26 n = pizza.size(), m = pizza[0].size(); 27 count = vector<vector<int>>(n + 1, vector<int>(m + 1, 0)); 28 29 for (int i = n - 1; i >= 0; i--) 30 for (int j = m - 1; j >= 0; j--) 31 count[i][j] = count[i + 1][j] + count[i][j + 1] - count[i + 1][j + 1] + (pizza[i][j] == 'A'); 32 33 return rec(0, 0, k - 1); 34 } 35 };