class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
int n = nums.size();
if (n==0) return nums;
int m = nums[0].size();
if (m==0) return nums;
if (n*m != r*c) return nums;
vector<vector<int>> ans(r, vector<int>(c, 0));
int a = 0, b = 0;
for (auto row: nums)
for (auto n: row) {
ans[a][b] = n;
b ++;
if (b == c) {
b = 0;
a ++;
}
}
return ans;
}
};


s[i] = nums[0]+...+nums[i]

{(i, j): 0 &lt=i &lt=j &lt nums.size(), s[j]-s[i-1]=k}

class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
int s = 0, ans = 0;
cnt[0] = 1;
for (int n: nums) {
s += n;
ans += cnt[s-k];
cnt[s] ++;
}
return ans;
}
};


class Solution {
public:
bool checkInclusion(string s1, string s2) {
vector<char> v1(26, 0), v2(26, 0);
int n = s1.length(), m = s2.length();
if (n>m) return false;
for (auto c: s1) v1[c-'a'] ++;
for (int i=0; i<n; i++)
v2[s2[i]-'a'] ++;
if (v1==v2) return true;
for (int i=n; i<m; i++)
{
v2[s2[i]-'a'] ++;
v2[s2[i-n]-'a'] --;
if (v1==v2) return true;
}
return false;
}
};


dp(i, j) = max(dp(i, j+1)+days[i][j+1]; dp(x, j+1)+days[x][j+1])

class Solution(object):
def maxVacationDays(self, flights, days):
"""
:type flights: List[List[int]]
:type days: List[List[int]]
:rtype: int
"""
n = len(flights)
k = len(days[0])

def dp(i, j, mf):
if j==k-1:
return 0;
if (i, j) in mf:
return mf[i, j]
ans = dp(i, j+1, mf) + days[i][j+1]
for x, b in enumerate(flights[i]):
if b==1:
ans = max(ans, dp(x, j+1, mf)+days[x][j+1])
mf[i, j] = ans
return ans

mf = {}
ans = dp(0, 0, mf) + days[0][0]
for x, b in enumerate(flights[0]):
if b==1:
ans = max(ans, dp(x, 0, mf)+days[x][0])
return ans