# Leetcode刷題學習筆記--Dynamic Programming
## Introduction
+ 可以從前一個狀態推展到目前的狀態?
+ 起始狀態是什麼?
## Problems
### [123. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)
> 1. 一開始我使用暴力破解，但是時間效率不是很好。
```cpp=
class Solution {
enum st{buy, sell};
int helper(vector<int>& prices, int idx, int tr, int prev) {
if(idx == prices.size() || tr == 2) return 0;
if(~mem[idx][tr][prev]) return mem[idx][tr][prev];
int donothing = helper(prices, idx + 1, tr, prev);
int dotrans;
if(prev == sell) dotrans = helper(prices, idx + 1, tr, buy) - prices[idx]; // buy
else dotrans = helper(prices, idx + 1, tr +
1, sell) + prices[idx]; // sell
return mem[idx][tr][prev] = max(dotrans, donothing);
}
vector<vector<vector<int>>> mem;
public:
int maxProfit(vector<int>& prices) {
int sz = prices.size();
mem.resize(sz, vector<vector<int>>(2, vector<int>(2, -1)));
return helper(prices, 0, 0, sell);
}
};
```
> 2. 根據官方的解答。這個題目會限制最多兩次，是因為我們可以退化成一次。
> 3. 如果是一次的話，就是一直找自己前面的最小值。
> 4. 兩次的意思是，你可以把vector切成前半部和後半部，分別找出最大的profit。
```cpp=
class Solution {
public:
int maxProfit(vector<int>& prices) {
int sz = prices.size();
if(sz <= 1) return 0;
int leftMin = prices[0];
int rightMax = prices[sz - 1];
vector<int> bwd(sz), fwd(sz + 1);
// 站在i的位置，往後看，會得到的最大profit
for(int i = 1; i < sz; ++i) {
bwd[i] = max(bwd[i - 1], prices[i] - leftMin);
leftMin = min(leftMin, prices[i]);
}
// 站在j的位置，往前看，會得到的最大profit
for(int j = sz - 2; j >= 0; --j) {
fwd[j] = max(fwd[j + 1], rightMax - prices[j]);
rightMax = max(rightMax, prices[j]);
}
int ans{0};
for(int i = 0; i < sz; ++i)
ans = max(ans, bwd[i] + fwd[i + 1]);
return ans;
}
};
```
> 5. 官方的另一種更optimal的想法是，把第一次得到的profit當成是下一次price價格減少。
```cpp=
class Solution {
public:
int maxProfit(vector<int>& prices) {
int t1min = 1e5, t1prof{0}, t2min = 1e5, t2prof{0};
for(auto& p : prices) {
t1min = min(t1min, p);
t1prof = max(t1prof, p - t1min);
// 因為從t1賺的錢，等於是第二次交易，買入價錢減少
t2min = min(t2min, p - t1prof);
t2prof = max(t2prof, p - t2min);
}
return t2prof;
}
};
```
### [1125. Smallest Sufficient Team](https://leetcode.com/problems/smallest-sufficient-team/description/)
> 1. 參考[lee215大的解答](https://leetcode.com/problems/smallest-sufficient-team/solutions/334572/java-c-python-dp-solution/?orderBy=most_votes)。
> 2. 這題很棒，對DP會有更深的理解。必做。
> 3. 當選中第i個people的時候，如果把第i個人加入任一個team都會使整體的skill發生變化。
> 4. 但是第i個人加入的前提是，加入後的人數比加入前的人數還要少。
```cpp=
class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
int n = req_skills.size();
unordered_map<string, int> shift;
for(int i = 0; i < req_skills.size(); ++i)
shift[req_skills[i]] = i;
// 選中的team所有的skill，最小的team
unordered_map<int, vector<int>> m;
// 避免hash collision
m.reserve(1 << n);
for(int i = 0; i < people.size(); ++i) {
int skill{0};
for(auto& s : people[i]) skill |= 1 << shift[s];
for(auto& ref : m) {
int comb = ref.first | skill;
if(!m.count(comb) || m[comb].size() > m[ref.first].size() + 1) {
m[comb] = m[ref.first];
m[comb].push_back(i);
}
}
m[skill] = {i};
}
return m[(1 << n) - 1];
}
};
```
### [1908. Game of Nim](https://leetcode.com/problems/game-of-nim/description/)
給你一個vector<int> piles，讓alice和bob輪流玩這個遊戲，每次可以從任意非零的stack中移除最少1個最多全部piles[i]，不能移動的那個palyer就是輸。返回alice使否會贏。這邊的前提是player都是optimal，也就是palyer會選對自己最有利的狀態。
> 1. 這題算是萬用題。怎麼說。因為任何題目都可以使用暴力破解，也就是列舉所有的可能性。最後再透過memorization來降低複雜度。
> 2. 這邊的暴力破解就是列舉所以可能的state，一個一個去嘗試，直到有結果。
> 3. 因為player是optimal的，如果你是player一定會選一個對自己最有利的狀況，也就是會下一手讓對手沒機會贏的狀態。也就是這個nextState對手沒機會贏。
> 4. isNextPlayerWin(vector<int>& nextState)定義為，使用nextState這個狀態，對方是否有機會贏。只要一有機會就是return true。因為這樣才能判斷是否是一定可以贏的狀態。
```cpp=
class Solution {
string getKey(const vector<int>& piles) {
ostringstream oss;
for(auto& n : piles) oss << n << "-";
return oss.str();
}
bool isNextPlayerWin(vector<int>& piles) {
string key = getKey(piles);
if(m.count(key)) return m[key];
for(int i = 0; i < piles.size(); ++i) {
for(int j = 1; j <= piles[i]; ++j) {
vector<int> nextState(piles);
nextState[i] -= j;
sort(nextState.begin(), nextState.end()); // 排序很重要，避免重複的計算
if(!isNextPlayerWin(nextState)) { //nextState 對方絕對不會贏，就會採取這個策略，
// 因為選手是optimal
return m[key] = true;
}
}
}
// 沒有一種狀態是"一定"會贏的，所以return false
return m[key] = false;
}
unordered_map<string, bool> m;
public:
bool nimGame(vector<int>& piles) {
m[getKey(vector<int>(piles.size()))] = 0;
return isNextPlayerWin(piles); // the first Next Player is Alice
}
};
```
### [96. Unique Binary Search Trees(Medium)](https://leetcode.com/problems/unique-binary-search-trees/)
給定一個數字n，則1~n之間可以組成多少個Binary Search Tree.首先Binary search tree的定義是:
> 左邊的BTS一定都比root還小。
> 右邊的BTS一定都比root還大。
n = 1時，結果為1。
n = 2時，有兩個數字[1,2]，當1為root時，2只能為右邊node。當
2為root時，1只能為左邊node，所以結果為2。
n = 3時，有三個數字[1,2,3]，
當1為root時，[]左邊子樹沒有，[2,3]的排列為右邊子樹。
當2為root時，[1]為左邊子樹， [3]為右邊子樹。
當3為root時，[1,2]的排列左邊子樹，[]右邊子樹沒有。
可以看出規律，[左邊子樹個數，右邊子樹個數]
dp[3] = [0, 2] + [1, 1] + [2, 0]
因為左右兩邊相乘的關係，所以dp[0] = 1。
```cpp=
int numTrees(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
for(int i = 1; i < n + 1; ++i) {
for(int j = 0; j < i; ++j)
dp[i] += dp[j] * dp[i - 1 - j];
}
return dp.back();
}
```
### [368. Largest Divisible Subset(Medium)](https://leetcode.com/problems/largest-divisible-subset/)
給你一個vector<int> nums，找出最大的subset滿足，任兩個數都是倍數關係。並且輸出這個subset。
例如 : nums = [1, 2, 3];可以得到兩個subset[1, 2]和[1, 3]，其中1和3為倍數關係，1和2為倍數關係。
解題思路:
> 1. 先排序，這樣只需要找比自己小的數字即可。
> 2. 使用DP，可以算出最大的subset。
> 3. 如果還要輸出subset內容，就要另外一個vector來記錄前一個節點。
```cpp=
vector<int> largestDivisibleSubset(vector<int>& nums) {
auto n = nums.size();
if (n == 1) return nums; // 只有一個不用計算直接return
sort(nums.begin(), nums.end()); // 排序
vector<int> dp(n, 1);
vector<int> idx(n, -1);
int maxidx{0};
int maxlength{0};
for(int i = 1; i < n; ++i) {
for(int j = 0; j < i; ++j) { // 只找比i還小的數
if(nums[i] % nums[j] == 0) { // 倍數關係
if(dp[j] + 1 > dp[i]) { // 比現在還大
dp[i] = dp[j] + 1;
idx[i] = j; // 紀錄前一個node
}
}
}
if(dp[i] > maxlength) { //找出最大subset
maxlength = dp[i];
maxidx = i;
}
}
vector<int> ans;
ans.push_back(nums[maxidx]);
int p = idx[maxidx];
while(p != -1) {
ans.push_back(nums[p]);
p = idx[p];
}
return ans;
}
```
### [152. Maximum Product Subarray(Medium)](https://leetcode.com/problems/maximum-product-subarray/)
給你一個vector<int>找出，subarray中相乘數字最大的值。
> 1. subarray為連續的element.
> 2. 最大值 = (負數) * (負最大值) or (正數) * (正最大值)
> 3. 必須同時記錄"負最大值"和"正最大值"。
```cpp=
int maxProduct(vector<int>& nums) {
auto n = nums.size();
int curr_max, curr_min, maxval;
maxval = curr_max = curr_min = nums[0];
for(int i = 1; i < n; ++i) {
int tmp = curr_max;
curr_max = max(nums[i], max(nums[i] * curr_max, nums[i] * curr_min));
curr_min = min(nums[i], min(nums[i] * tmp, nums[i] * curr_min));
maxval = max(maxval , curr_max);
}
return maxval;
}
```
### [213. House Robber II(Medium)](https://leetcode.com/problems/house-robber-ii/)
這題是[198. House Robber](https://leetcode.com/problems/house-robber/)的延伸。除了相鄰點不可以偷之外，還多了頭尾相接的條件。
> 1. 解法和House Robber一樣，但是最後的node必須根據node-0有沒有偷來決定，所以使用兩個array來記錄。
> 2. 一個array紀錄有偷node-0，一個array來記錄沒偷node-0。
> 3. ==初始化array就變的很重要，因為偷了node-0，所以rob0[1]就不能偷。==
```cpp=
int rob(vector<int>& nums) {
auto n = nums.size();
if(n == 1) return nums[0];
if(n == 2) return max(nums[0], nums[1]);
vector<int> rob0(n, 0);
vector<int> rob1(n, 0);
rob0[0] = nums[0];
rob0[1] = rob0[0]; // important
rob1[1] = nums[1];
for(int i = 2; i < n; ++i) {
if(i == n - 1) {
rob0[i] = rob0[i - 1];
rob1[i] = max(rob1[i - 2] + nums[i], rob1[i - 1]);
} else {
rob0[i] = max(rob0[i - 2] + nums[i], rob0[i - 1]);
rob1[i] = max(rob1[i - 2] + nums[i], rob1[i - 1]);
}
}
return max(rob0[n - 1], rob1[n - 1]);
}
```
### [337. House Robber III(Medium)](https://leetcode.com/problems/house-robber-iii/)
給一個binary tree，規則一樣如果偷相鄰兩個node就會通報警察。求出在不通報警察的情況下，可以得到的最佳金額。
> 1. 一開始我用house robber的想法去解，從root推到leaf會遇到沒辦法求出最佳報酬的問題。因為會有加入重複數字的問題。
> 2. 最好的解髮是從leaf推展到root，這樣就不會有加入重複數字的問題。
> 3. ==關鍵在於"不打劫"這個節點，則子節點也不一定要打劫。==
```cpp=
class Solution {
int rub = 0;
int norub = 1;
public:
int rob(TreeNode* root) {
vector<int> rtn = dfs(root);
return max(rtn[rub], rtn[norub]);
}
vector<int> dfs(TreeNode *root) {
if(!root) return vector<int>(2, 0);
vector<int> left = dfs(root->left);
vector<int> right = dfs(root->right);
vector<int> rtn(2, 0);
// 打劫這個node，則兩個子節點就不能打劫。
rtn[rub] = left[norub] + right[norub] + root->val;
// 不打劫這個node，則可打劫子節點，也可以不打劫子節點
// 因為是要最大的報酬，所以取最大值。
rtn[norub] = max(left[norub], left[rub]) + max(right[norub], right[rub]);
return rtn;
}
};
```
### [740. Delete and Earn(Medium)](https://leetcode.com/problems/delete-and-earn/)
題目是想從array中找出最大的points，但是每次取一個數num，就必須把前後的數砍掉(num - 1, num + 1)。
> 1. 這個問題其實也是House Robber，因為相鄰的數字不能取。
> 2. 解題的重點是使用了一個vector<int>(10001, 0)，因為題目跟我們說數字的值域從1到10000。
> 3. 可以使用map但是相對的判斷和前後取值會麻煩很多。
```cpp=
int deleteAndEarn(vector<int>& nums) {
vector<int> sums(10001, 0);
for (int num : nums) sums[num] += num;
for (int i = 2; i < 10001; ++i) {
sums[i] = max(sums[i - 1], sums[i - 2] + sums[i]);
}
return sums[10000];
}
```
> 1. 因為數字分散，所以先使用map來統計每個數字有幾個。
> 2. traverse整個map，如果目前和前一個差1就只能選目前，或是前兩個。
```cpp=
int deleteAndEarn(vector<int>& nums) {
map<int, int> m;
//統計每個數字出現的次數
for(auto& n : nums)
m[n]++;
auto n = m.size();
vector<int> dp(n);
// 取第一個最小的數字
auto it = m.begin();
dp[0] = it->first * it->second; it++;
for(int i = 1; i < n; ++i, ++it) {
int cur = it->first * it->second;
// 如果和前一個數字差一
if(it->first == (prev(it)->first + 1)) {
// special case,只有兩個數字，就是看要取哪一個最大
if(i == 1)
dp[i] = max(dp[i - 1], cur);
else
dp[i] = max(dp[i - 1], cur + dp[i - 2]);
} else
dp[i] = dp[i - 1] + cur; // 和前面數字不是差一，所以可以拿
}
return dp.back();
}
```
### [5. Longest Palindromic Substring(Medium)](https://leetcode.com/problems/longest-palindromic-substring/)
給你一個字串s，找出當中最長的回文子字串。
> 1. 每個字母都是長度1的回文。
> 2. 長度2的回文，兩個字母都一樣。
> 3. 長度3以上的回文，去掉頭尾也是回文。
```
string longestPalindrome(string s) {
auto n = s.length();
if(n == 1) return s;
int len{1}, idx{0};
// declare an array
int dp[n][n];
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
dp[i][j] = 0;
for(int right = 0; right < n; ++right) {
dp[right][right] = 1;
for(int left = 0; left < right; ++left) {
if(s[left] != s[right]) continue;
int ll = right - left + 1;
// 長度3以上的回文，去掉頭尾也是回文。
if(ll > 2 && dp[left + 1][right - 1])
dp[left][right] = max(dp[left + 1][right - 1] + 2, dp[left][right]);
// 如果長度只有2
if(ll == 2)
dp[left][right] = max(2, dp[left][right]);
// 如果是回文，也長度(ll)比len還大，更新len和idx
if(dp[left][right] && ll > len) {
len = ll;
idx = left;
}
}
}
return s.substr(idx, len);
}
```
2022/1/31
> 1. 因為迴文是從string中選出left和right，所以一個迴文用兩個變數來表示，使用2D DP。
```cpp=
string longestPalindrome(string s) {
auto n = s.length();
vector<vector<int>> dp(n, vector<int>(n));
int idx{0}, maxlen{1}, right, left;
for(right = 0; right < n; ++right) {
// 只有一個char一定是回文
dp[right][right] = 1;
for(left = 0; left < right; ++left) {
// 當左右都是一樣，且長度小於等於3或是left, right縮小一個也是回文
dp[left][right] = (s[left] == s[right] && (right - left <= 2 || dp[left + 1][right - 1]));
// 紀錄最長的情況
if(dp[left][right] && right - left + 1 > maxlen) {
maxlen = right - left + 1;
idx = left;
}
}
}
return s.substr(idx, maxlen);
}
```
2022/06/14
用一個vector<vector<int>> dp來記錄，從i到j的substring是不是palindrome。簡單不容易出錯的方法就是好方法。
```cpp=
string longestPalindrome(string s) {
int sz = s.size();
if(sz == 1) return s;
vector<vector<int>> dp(sz, vector<int>(sz));
int maxlen = 1, idx = 0;
// dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1])
// 因為dp[i + 1][j - 1] 所以i由大到小，j由小到大
for(int i = sz - 1; i >= 0; --i) {
for(int j = i; j < sz; ++j) {
if(i == j) dp[i][j] = 1;
else if(i + 1 == j) {
if(s[i] == s[j]) dp[i][j] = 1;
} else {
dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
}
if(dp[i][j] && j - i + 1 > maxlen) {
maxlen = j - i + 1;
idx = i;
}
}
}
// time complexity : O(N^2)
// space complexity : O(N^2)
return s.substr(idx, maxlen);
}
```
### [91. Decode Ways(Medium)](https://leetcode.com/problems/decode-ways/)
A->1, B->2, C->3，以此類推到Z->26，可以編碼成一串數字。試問這串數字有幾種解碼方式。
> 1. 自己可以解碼(s[i] != 0)，則解碼的方式和dp[i - 1]一樣。
> 2. 自己可以和前面合併起來解碼(10~26)，則解碼的方式和dp[i - 2]一樣。
> 3. 把這兩種相加就是從0~i的解碼方式dp[i]。
```cpp=
int numDecodings(string s) {
auto n = s.length();
if(n == 0 || s[0] == '0') return 0;
vector<int> dp(n);
dp[0] = 1;
for(int i = 1; i < n; ++i) {
// s[i]可以自己一個解碼，所以有dp[i - 1]種組合
dp[i] += (s[i] == '0' ? 0 : dp[i - 1]);
// s[i]可以和前面合併一起解碼，所以有dp[i - 2]種組合
if(s[i - 1] == '1' || (s[i - 1] =='2' && s[i] <= '6'))
dp[i] += (i>= 2 ? dp[i - 2] : 1);
}
return dp[n - 1];
}
```
### [1143. Longest Common Subsequence(Medium)](https://leetcode.com/problems/longest-common-subsequence/)
給你兩個字串text1和text2，求出兩個共同的subsequence最大值。
subsequence定義就是char出現的順序不變，但是在text中不用連續。
> 1. dp[i][j]的定義是text1[0-i]和text2[0-j]共同的subsequence的最大長度。
> 2. case 1 : 如果text1[i] == text2[j]，則dp[i][j] = dp[i - 1][j - 1] + 1;
> 3. case 2 : 如果text1[i] != text2[j]，則dp[i - 1][j]和dp[i][j - 1]選一個最大的。
> 4. 因為都會存取i - 1或是j - 1，所以vector的大小給大一點(n + 1)。
```cpp=
int longestCommonSubsequence(string text1, string text2) {
auto n1 = text1.length();
auto n2 = text2.length();
vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
int rtn{0};
for(int i = 1; i < n1 + 1; ++i) {
for(int j = 1; j < n2 + 1; ++j) {
if(text1[i - 1] == text2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
rtn = max(rtn, dp[i][j]);
}
}
return rtn;
}
```
### [72. Edit Distance(Hard)](https://leetcode.com/problems/edit-distance/)
給你兩個字串word1和word2，一次可以replace, insert和delete一個字元，求最小的次數可以把word1變成word2。
```cpp=
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i <= m; ++i) dp[i][0] = i;
for (int i = 0; i <= n; ++i) dp[0][i] = i;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
// 字元相同，則不用作任何操作。
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
//字元不同，則為了讓word1[0-i]等於word2[0-j]，
//使用了 replace, delete,insert的最小值
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
}
}
return dp[m][n];
}
```
### [983. Minimum Cost For Tickets(Medium)](https://leetcode.com/problems/minimum-cost-for-tickets/)
給你一個vector<int> days來表示一年中1~365哪一天會去旅行。另外vector<int> costs來表示1日卷，7日卷，和30日卷的價錢，求出旅行完days規定的天數後，最小的cost。
> 1. 因為需要檢查days的天數，所以放入set可以快速檢視是否在days裡面。
> 2. 這一天(day)的旅費是 day - 1使用1日卷，或是day-7使用7日卷，或是day-30使用30日卷的最小值。
> 3. 如果這一天不旅行，則旅費和前一天一樣。
```cpp=
int mincostTickets(vector<int>& days, vector<int>& costs) {
// 放入set就不用一直檢查是否有重複的數字
unordered_set<int> s(days.begin(), days.end());
int lastday = days.back();
vector<int> dp(lastday + 1);
for(int i = 1; i <= lastday; ++i) {
if(s.count(i)) {
// 檢查買1日, 7日或是30日比較划算
// 使用max(0, i - 7) 來避免取到負數
dp[i] = min(dp[max(0, i - 1)] + costs[0],
min(dp[max(0, i - 7)] + costs[1], dp[max(0, i - 30)] + costs[2]));
} else
dp[i] = dp[i - 1]; // 和前一日一樣
}
return dp.back();
}
```
### [518. Coin Change 2](https://leetcode.com/problems/coin-change-2/)
給你數個coins，求出可以排列成target的組合數目。
```cpp=
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int coin : coins) {
// 這邊從最前面找到最後面，因為可以重複使用coins中的數字
for (int i = coin; i <= amount; ++i) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
```
另一種top-down的做法，每一個coins可以選擇要不要取。所以有兩個選項。
```cpp=
class Solution {
int helper(int amount, vector<int>& coins, int idx) {
if(amount == 0) return 1;
if(idx == -1) return 0;
if(mem[amount][idx] > -1) return mem[amount][idx];
int rtn;
int nochange = helper(amount, coins, idx - 1);
int dochange = 0;
if(coins[idx] <= amount)
dochange = helper(amount - coins[idx], coins, idx);
return mem[amount][idx] = nochange + dochange;
}
vector<vector<int>> mem;
public:
int change(int amount, vector<int>& coins) {
int sz = coins.size();
mem.resize(amount + 1, vector<int>(sz, -1));
return helper(amount, coins, sz - 1);
}
};
```
==不可以重複使用的情況，請參考[Target Sum](/FbvqYdi1SsCc-R96j0jVAA#494-Target-Sum)==
### [2218. Maximum Value of K Coins From Piles](https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/)
給你k個piles，每個piles像一個stack一樣，只能依序從第一個開始拿，你只能拿k個coins，試問可以拿到的最大值。
> 1. 因為最多可以拿k個，
> 2. 所以對第一個piles來說有k+1個選項，不拿(0)，拿一個(1),...拿k個(k)。
> 3. 當第一個piles拿了n個，則後面piles只能分配到k - n個。
> 4. 所以helper的兩個input argument，第一個為目前在的piles，第二個為還剩下多少個k
> 5. 和[Coin change2](https://hackmd.io/474VEENxSVSGMRRRtfvetQ#518-Coin-Change-2)類似，只是現在每一個有k+1個選項。
```cpp=
class Solution {
int sz;
vector<vector<int>> mem;
int helper(vector<vector<int>>& piles, int from, int k) {
if(from == sz || k == 0) return 0;
if(mem[from][k] > 0) return mem[from][k];
int res = helper(piles, from + 1, k); // 不取
int cur = 0;
//從piles from取1個,2個...N個
for(int i = 0; i < min((int)piles[from].size(), k); ++i) {
cur += piles[from][i];
//改取下一個piles，且剩下k - i - 1 coins
res = max(res, helper(piles, from + 1, k - i - 1) + cur);
}
return mem[from][k] = res;
}
public:
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
this->sz = piles.size();
mem.resize(sz, vector<int>(k + 1));
return helper(piles, 0, k);
}
};
```
2023/04/15 daily challenge但是寫出了TLE的解答。
> 1. 當初的想法是，每個piles有兩種可能，拿或是不拿
> 2. 因為只用了拿和不拿，所以必須知道拿到第幾個。
> 3. 所以先把piles反轉，從後面決定拿與不拿。
> 4. 這樣其實條件比較複雜，因為每次會跟當下的piles相關。
```cpp=
class Solution {
int helper(vector<vector<int>>& piles, int k) {
if(k == 0) return 0;
int ans{0};
for(auto& p : piles) {
if(p.size() == 0) continue;
int back = p.back();
p.pop_back();
int take = helper(piles, k - 1) + back;
p.push_back(back);
ans = max(ans, take);
}
return ans;
}
public:
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
for(auto& p : piles)
reverse(p.begin(), p.end());
return helper(piles, k);
}
};
```
參考了[lee215的解答](https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/solutions/1887010/java-c-python-top-down-dp-solution/?orderBy=most_votes)。
> 1. 其實想法和上面每個piles取與不取類似。
> 2. 從一個piles[i]的角度來看所有的組合就是，取0個, 取1個 到 取min(piles[i].size(), k)
> 3. 所以從上面所有的組合中再看helper(piles, idx + 1, rem - j - 1) 的所有組合。
```cpp=
class Solution {
int n;
int helper(vector<vector<int>>& piles, int idx, int rem) {
if(idx == n || rem == 0) return 0;
if(mem[idx][rem]) return mem[idx][rem];
// ans 從取0個開始
int cur{0}, ans = helper(piles, idx + 1, rem);
// 取1個，取2個，...，取min(piles[idx], rem)個
for(int j = 0; j < rem && j < piles[idx].size(); ++j) {
cur += piles[idx][j];
ans = max(ans, helper(piles, idx + 1, rem - j - 1) + cur);
}
return mem[idx][rem] = ans;
}
vector<vector<int>> mem;
public:
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
n = piles.size();
mem.resize(n, vector<int>(k + 1));
return helper(piles, 0, k);
}
};
```
### [2420. Find All Good Indices](https://leetcode.com/problems/find-all-good-indices/)
判斷是否為good indices。條件是在第i個的前k個是遞減數列，後k個是遞增數列。
> 1. 只會使用brust force結果就TLE。
> 2. 再來想到用2D DP(vector<vector<bool>>)來記錄開始和結束是遞增或是遞減，但是這樣做沒什麼效率。可能是想到判斷回文的關係。
> 3. 使用1D DP來記錄到目前為止，遞增或是遞減的數列長度。
> 4. 最後只要判斷i的前後是否大於等於k即可。
```cpp
vector<int> goodIndices(vector<int>& nums, int k) {
int sz = nums.size();
vector<int> fwd(sz, 1), bwd(sz, 1);
for(int i = 1, j = sz - 2; i < sz; ++i, --j)
if(nums[i] <= nums[i - 1]) fwd[i] = fwd[i - 1] + 1;
for(int i = sz - 2; i >= 0; --i)
if(nums[i] <= nums[i + 1]) bwd[i] = bwd[i + 1] + 1;
vector<int> ans;
for(int i = k; i < sz - k; ++i) {
if(fwd[i - 1] >= k && bwd[i + 1] >= k)
ans.push_back(i);
}
return ans;
}
```
### [1031. Maximum Sum of Two Non-Overlapping Subarrays](https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/description/)
> + 因為fistLen和secondLen可以在任意位置，不好思考。
> + 先假設firstLen一定在secondLen的前面。
> + 則在 idx = i 的時候，後面subarray的firstLen最大值 + 前面subarray的secondLen的最大值和，
> + 即為 idx = i 的時候的最好情況，所以我們要找出所有index的情況
> + 在考慮 secondLen和firstLen的情況。
> + 為什麼是dynamic programming? 因為dp1[i] = max(dp[i - 1], sum);每次都紀錄從i往前/往後看的最大值。
```cpp=
class Solution {
public:
int helper(vector<int>&nums,int x,int y){
int n=nums.size();
vector<int>dp1(n,0),dp2(n,0);
int sum=0;
for(int i=0;i<n;i++){
if(i<x){//when we haven't considered x-size array
sum+=nums[i];
dp1[i]=sum;
}
else{ //when we have a window of size x
sum=sum+nums[i]-nums[i-x];
dp1[i]=max(dp1[i-1],sum);
}
}
sum=0;
for(int i=n-1;i>=0;i--){
if(i+y>n-1) { //case when we haven't encountered a window of size secondlen ie. y
sum+=nums[i];
dp2[i]=sum;
}
else{//when we have a window of size secondLen
sum=sum+nums[i]-nums[i+y];
dp2[i]=max(dp2[i+1],sum);
}
}
int ans=0;
//our ans window will be from x-1 to n-y
for(int i=x-1;i<n-y;i++){
ans=max(ans,dp1[i]+dp2[i+1]);
}
return ans;
}
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen){
return max(helper(nums, firstLen, secondLen),helper(nums, secondLen, firstLen));
}
};
```
### [2466. Count Ways To Build Good Strings](https://leetcode.com/problems/count-ways-to-build-good-strings/)
> 1. why dynamic programming?
> 因為string長度為len的字串，可以從string長度為len - zero或是len - one來推得。
> 2. 建立string的條件就是在string後面增加某些zero或是某些one。
> 3. 為什麼要走訪全部的lenght直到high?
> 因為長度為len的string是由更短的字串所建立而成，所以必須要從長度為1開始走訪。
> 4. 從前一個狀態推展到目前狀態?
> ```cpp=
> if(i - zero > 0) dp[i] += dp[i - zero];
> if(i - one >= 0) dp[i] += dp[i - one];
> ```
> 5. 起始狀態，dp[0] = 1，因為當長度跟one或是zero一樣的時候，就是使用這個來建立字串。
```cpp=
class Solution {
// dynamic programming
// 從上一個狀態，推展到這個狀態
// 這個狀態就是長度i的string, 會得到這個長度的string有四種可能
// 1. 從 i - zero長度的string, append zero
// 2. 從 i - one 長度的string, append one
// 3. zero自己本身是長度i
// 4. one自己本身是長度i
unordered_map<int, int> m; // len, count
int mod = 1e9 + 7;
public:
int countGoodStrings(int low, int high, int zero, int one) {
/*
int ans = 0;
for(int i = 1; i <= high; ++i) {
if(m.count(i - zero)) m[i] = m[i - zero];
if(m.count(i - one)) m[i] = (m[i] + m[i - one]) % mod;
if(i == zero) m[i]++;
if(i == one) m[i]++;
//cout << i << "," << m[i] << endl;
if(i >= low) ans = (ans + m[i]) % mod;
}
return ans;
*/
vector<int> dp(high + 1); // len
dp[0] = 1;
int ans{0};
for(int i = 1; i <= high; ++i) {
if(i - zero >= 0) dp[i] = (dp[i] + dp[i - zero]) % mod;
if(i - one >= 0) dp[i] = (dp[i] + dp[i - one]) % mod;
if(i >= low) ans = (ans + dp[i]) % mod;
}
return ans;
}
};
// low = 2, high = 3, zero = 1, one = 2
// len = 1, 2, 3
// len = 1 -> 0
// len = 2 -> 00, 11
// len = 3 -> 000, 110, 011
```
### [1130. Minimum Cost Tree From Leaf Values](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/description/)
> + 一開始解不出來是因為題目沒弄懂。
> + left node是從array依序放入，重點是依序。
> + 往上傳是left或是right的最大值。
> + 因為需要同時知道sum和left/right的最大值，所以使用pair來當return值。
```cpp=
class Solution {
//sum, max(left, right)
pair<int, int> helper(vector<int>& arr, int i, int j) {
pair<int, int> rtn = {INT_MAX, INT_MAX};
if(~mem[i][j].first) return mem[i][j];
if(i == j) rtn = {0, arr[i]};
else {
for(int k = i; k < j; ++k) {
auto l = helper(arr, i, k);
auto r = helper(arr, k + 1, j);
// sum即為兩邊做大值的product加上兩邊的和
int sum = l.second * r.second + l.first + r.first;
if(rtn.first > sum) {
rtn.first = sum;
// 題意是說left或是right的最大值
rtn.second = max(l.second, r.second);
}
}
}
return mem[i][j] = rtn;
}
vector<vector<pair<int, int>>> mem;
public:
int mctFromLeafValues(vector<int>& arr) {
int sz = arr.size();
mem.resize(sz, vector<pair<int, int>>(sz, make_pair(-1, -1)));
return helper(arr, 0, sz - 1).first;
}
};
```
### [1262. Greatest Sum Divisible by Three](https://leetcode.com/problems/greatest-sum-divisible-by-three/description/)
給你一個vector<int>，返回最大的element sum，可以被3整除。
> 1. [Greedy的解法](https://hackmd.io/p9hSX0fpSQGwCUL3QF7cLA#1262-Greatest-Sum-Divisible-by-Three)是，全部加起來後，看餘數是多少減掉餘數最小的值。
> 2. 參考[lee215](https://leetcode.com/problems/greatest-sum-divisible-by-three/solutions/431077/java-c-python-one-pass-o-1-space/)的答案，發現DP才是最漂亮的解法。
> 3. 從第n個數值的角度來看，他可以和前面三種狀態(remain = 0, 1, 2)，組合出新的sum，並且更新vector<int> dp。
```cpp=
int maxSumDivThree(vector<int>& nums) {
vector<int> dp(3);
for(auto& n : nums) { // n和每個可能組合成一個新的
for(auto& i : vector<int>(dp)) { // copy constructor 因為我們取用的資料不能被update
dp[(i + n) % 3] = max(dp[(i + n) % 3], i + n);
}
}
return dp[0];
}
```
### [1911. Maximum Alternating Subsequence Sum](https://leetcode.com/problems/maximum-alternating-subsequence-sum/description/)
```cpp=
class Solution {
vector<vector<long long>> mem;
long helper(vector<int>& nums, int idx, int mul) {
if(idx == nums.size()) return 0;
int i = mul != -1;
if(mem[idx][i] != LONG_MIN) return mem[idx][i];
long long take = helper(nums, idx + 1, -mul) + nums[idx] * mul;
long long notake = helper(nums, idx + 1, mul);
return mem[idx][i] = max(take, notake);
// mem[idx][0] = max(mem[idx + 1][1] + nums[idx], mem[idx + 1][0]);
// mem[idx][1] = max(mem[idx + 1][0] - nums[idx], mem[idx + 1][1])
}
public:
long long maxAlternatingSum(vector<int>& nums) {
/* top-down : memorization
mem.resize(nums.size(), vector<long long>(2, LONG_MIN));
return helper(nums, 0, 1);
*/
// bottom-up : tabulation
/*enum st{even, odd};
vector<vector<long long>> dp(2, vector<long long>(nums.size() + 1));
for(int i = nums.size() - 1; i >= 0; --i) {
dp[even][i] = max(dp[even][i + 1], dp[odd][i + 1] + nums[i]);
dp[odd][i] = max(dp[odd][i + 1], dp[even][i + 1] - nums[i]);
}
return max(dp[even][0], dp[odd][0]);
// time complexity : O(N)
// space complexity : O(N)
*/
// reduce the space
long long even{}, odd{};
for(int i = nums.size() - 1; i >= 0; --i) {
even = max(even, odd + nums[i]);
odd = max(odd, even - nums[i]);
}
return max(even, odd);
// time complexity : O(N)
// space complexity : O(1)
}
};
```
### [1751. Maximum Number of Events That Can Be Attended II](https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended-ii/description/)
給你一個vector<vector<int>> events，其中有start, end和value, 選的events不能重疊，返回最大的value sum。
> + 因為選這個event必須和上一個不重疊
> 1. 一開始會用prev, current來表示，但是這樣就會多一個變數
> 2. 如果確定要選current，那下一個可以直接跳到**可以選擇**的next，而不是一個一個跳，這樣就可以避免使用兩個變數。
```cpp=
class Solution {
int n;
vector<vector<int>> dp;
enum st{start, end, value};
int helper(vector<vector<int>>& events, int cur, int k) {
if(cur == n || k == 0) return 0;
if(~dp[cur][k]) return dp[cur][k];
int next; // 找出如果選擇cur的下一個可以選擇的event
for(next = cur + 1; next < n; ++next)
if(events[cur][end] < events[next][start]) break;
return dp[cur][k] =
max(helper(events, cur + 1, k),
helper(events, next, k - 1) + events[cur][value]);
// dp[cur][k] = max(dp[cur + 1][k], dp[next][k - 1] + events[cur][value]);
// cur
// /|\
// k -->|
}
public:
int maxValue(vector<vector<int>>& events, int k) {
n = events.size();
dp.resize(n, vector<int>(k + 1, -1));// O(N)
sort(events.begin(), events.end()); // O(NlogN)
// 因為使用memorizationation把n, k的組合都找一次
// 所以是O(NK)，但是中間有找next的for loop
// 所以是O(NK*N)
// 如果找next改成binary search，則O(NKlogN)
// time : O(N + NlogN + NKN) = O(N^2K)
// space : O(NK)
return helper(events, 0, k);
}
};
```
### [1444. Number of Ways of Cutting a Pizza](https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/description/)
給你一個MxN的pizza，試問切成k等分，每個pizza都要有一個以上的蘋果，試問有多少種的切法。
> 1. 先定義切法，不管垂直切或是水平切，切下去之後的上方或是左方給出去，剩下的再繼續切。
> 2. 所以helper(y, x, k)，表示剩下的pizza從(y, x)開始到(m - 1, n - 1)。
> 3. 使用apples來統計從(y, x)往下看剩下的apples方便以後的計算。
> 4. dynamic programming其實也是一種暴力破解，只是有記憶功能。
```cpp=
class Solution {
int m, n, mod;
vector<vector<int>> apples;
int helper(int y, int x, int k) {
int& ans = mem[y][x][k];
if(~ans) return ans;
if(k == 1) return ans = apples[y][x] > 0;
else {
int ways{};
//cut horizontal
for(int i = y + 1; i < m; ++i) {
if(apples[y][x] - apples[i][x] > 0)
ways = (ways + helper(i, x, k - 1)) % mod;
}
// cur vertical
for(int i = x + 1; i < n; ++i) {
if(apples[y][x] - apples[y][i] > 0)
ways = (ways + helper(y, i, k - 1)) % mod;
}
return ans = ways;
}
}
vector<vector<vector<int>>> mem;
public:
int ways(vector<string>& pizza, int k) {
m = pizza.size();
n = pizza[0].size();
mod = 1e9 + 7;
apples.resize(m + 1, vector<int>(n + 1));
for(int y = m - 1; y >= 0; --y) // O(MN)
for(int x = n - 1; x >= 0; --x)
apples[y][x] = apples[y + 1][x] + apples[y][x + 1] - apples[y + 1][x + 1]
+ (pizza[y][x] == 'A');
mem.resize(m, vector<vector<int>>(n, vector<int>(k + 1, -1)));
return helper(0, 0, k);
// time : O(MNK)
// space : O(MN + MNK)
}
};
```
### [1048. Longest String Chain](https://leetcode.com/problems/longest-string-chain/description/?envType=daily-question&envId=2023-09-23)
找出最長的string chain，string chain的定義是，字串刪掉一個char會等於前一個字串。
> 1. 因為string chain是字數少的在前面，所以對words針對size排序。
> 2. 嘗試所有刪掉一個char的可能，來找出前一個string。
```cpp=
int longestStrChain(vector<string>& words) {
sort(begin(words), end(words), [](auto& str1, auto& str2){ // O(NlogN)
return str1.size() < str2.size();
});
unordered_map<string, int> m;
int ans{};
for(auto& w : words) { // O(NM)
for(int i = 0; i < w.size(); ++i) {
string prev = w.substr(0, i) + w.substr(i + 1);
m[w] = max(m[w], m[prev] + 1);
}
ans = max(ans, m[w]);
}
return ans;
// time : O(NM + NlogN) = O(NM)
// space : O(logN + N) = O(N)
}
```
### [2646. Minimize the Total Price of Trips](https://leetcode.com/problems/minimize-the-total-price-of-the-trips/description/)
給你一個undirected graph，每個node都有不同的price。給你一個vector<vector<int>> Trips，求所有路徑經過node的和為最小。在開始前可以==把不相鄰的node價錢砍半==。
> 1. 統計每個node經過的次數。
> 2. 不相鄰的node價錢砍半，和house robber一樣，
如果parent node價錢砍半，則child node價錢一定不能砍半。
如果parent node價錢沒砍半，則child node可以砍半，也可以不砍半。
> 3. 使用dynamic programming來找出最小值。
> 4. 為什麼memory vector不需要紀錄parent?
因為parent在之後的f()用不到。
```cpp=
class Solution {
unordered_map<int, vector<int>> adj;
vector<int> freq;
vector<vector<int>> mem;
bool dfs(int p, int s, int e) {
if(s == e) return true;
for(auto& nxt : adj[s]) {
if(nxt == p) continue;
freq[nxt]++;
if(dfs(s, nxt, e)) return true;
freq[nxt]--;
}
return false;
}
// 為什麼mem不需要紀錄parent?
// helper(node, parent, parentHalved) = f(helper(nxt, node, 0), helper(nxt, node, 1))
// f() 中不需要使用parent，parent是由node取代，nxt也是由node得到
// 所以mem不須紀錄parent
int helper(vector<int>& price, int node, int parent = -1, int parentHalved = 0) {
if(~mem[node][parentHalved]) return mem[node][parentHalved];
int res1 = freq[node] * price[node] / 2;
int res2 = freq[node] * price[node];
for(auto& nxt : adj[node]) {
if(nxt == parent) continue;
res2 += helper(price, nxt, node, 0);
}
if(parentHalved) return mem[node][parentHalved] = res2; // 如果parent價錢砍半，則目前的node不能砍半
for(auto& nxt : adj[node]) {
if(nxt == parent) continue;
res1 += helper(price, nxt, node, 1);
}
return mem[node][parentHalved] = min(res1, res2); // 如果parent價錢沒砍半，則目前的node可以砍半，或是不用砍半
}
public:
int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
for(auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
freq.resize(n);
for(auto& t : trips) {
freq[t[0]]++;
dfs(-1, t[0], t[1]);
}
mem.resize(n, vector<int>(2, -1));
return helper(price, 0);
}
};
```
### [1239. Maximum Length of A Concatenated String with Unique Characters](https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/description)
> 這題可以使用不同形式的DP來求解，重點是如何快速判斷string之間有unique char，使用bit manipulation。
```cpp=
class Solution {
vector<int> alpha, unique;
int helper(int val, int idx) {
if(idx == alpha.size()) return __builtin_popcount(val);
else if(!unique[idx]) return helper(val, idx + 1);
else {
int notake = helper(val, idx + 1);
int take{};
if((val & alpha[idx]) == 0) take = helper(val | alpha[idx], idx + 1);
return max(take, notake);
}
}
public:
int maxLength(vector<string>& arr) {
int sz = arr.size();
alpha.resize(sz);
unique.resize(sz, true);
for(int i = 0; i < sz; ++i) {
for(auto& c : arr[i]) {
int shift = 1 << (c - 'a');
if(alpha[i] & shift) // duplicate in this word
unique[i] = false; // never take this word
alpha[i] |= 1 << (c - 'a');
}
}
int val{}, idx{};
return helper(val, idx);
}
};
```
> 參考lee215的解答
```cpp=
class Solution {
public:
int maxLength(vector<string>& arr) {
vector<bitset<26>> dp = {bitset<26>()}; // default : put one emoty bitset
int res{};
for(auto& s : arr) {
bitset<26> a;
for(auto& c : s)
a.set(c - 'a');
if(a.count() < s.size()) continue;
for(int i = dp.size() - 1; i >= 0; --i) { // 從後面開始取就不會有重複問題
bitset c = dp[i];
if((c & a).any()) continue; // c 和 a有交集
dp.push_back(c | a);
res = max(res, (int)c.count() + (int)a.count());
}
}
return res;
}
};
```
### [1043. Partition Array for Maximum Sum](https://leetcode.com/problems/partition-array-for-maximum-sum/)
```cpp=
class Solution {
int sz, k;
// 從idx往後看有那些可能?
// subarray size = 1, 2, 3, ... k
// 嘗試每一種可能的subarray。
int helper(vector<int>& arr, int idx) {
if(~mem[idx]) return mem[idx];
int ans{}, maxv{};
for(int i = idx; i < idx + k && i < arr.size(); ++i) {
maxv = max(maxv, arr[i]);
ans = max(ans, maxv * (i - idx + 1) + helper(arr, i + 1));
}
return mem[idx] = ans;
}
vector<int> mem;
public:
int maxSumAfterPartitioning(vector<int>& arr, int k) {
sz = arr.size();
this->k = k;
mem.resize(sz + 1, -1);
mem.back() = 0;
return helper(arr, 0);
}
};
```
### [1696. Jump Game VI](https://leetcode.com/problems/jump-game-vi/)
top down + memory -> TLE
```cpp=
class Solution {
int helper(vector<int>& nums, int k, int idx) {
if(mem[idx] != INT_MIN) return mem[idx];
int ans = INT_MIN;
for(int nxt = idx + 1; nxt <= min(idx + k, (int)nums.size() - 1); ++nxt) {
ans = max(ans, nums[idx] + helper(nums, k, nxt));
}
return mem[idx] = ans;
}
vector<int> mem;
public:
int maxResult(vector<int>& nums, int k) {
//因為答案有可為-1，所以改成INT_MIN
mem.resize(nums.size(), INT_MIN);
mem.back() = nums.back();
return helper(nums, k, 0);
}
// time : O(NK)
// space : O(N)
};
```
改成bottom-up tabulation 也是TLE，因為time complexity一樣。
```cpp=
class Solution {
public:
int maxResult(vector<int>& nums, int k) {
vector<int> dp(nums.size(), INT_MIN);
dp.back() = nums.back();
for(int i = nums.size() - 2; i >= 0; --i) {
for(int nxt = i + 1; nxt <= min(i + k, (int)nums.size() - 1); ++nxt)
dp[i] = max(dp[i], nums[i] + dp[nxt]);
}
return dp.front();
// time : O(NK)
// space : O(N)
}
}
```
因為是找後k個最大值，所以可以使用multiset，可以降低複雜度
```cpp=
class Solution {
public:
int maxResult(vector<int>& nums, int k) {
vector<int> dp(nums.size());
multiset<int> ms{dp.back() = nums.back()};
for(int i = nums.size() - 2; i >= 0; --i) {
if(i + k + 1 < nums.size()) ms.erase(ms.find(dp[i + k + 1]));
dp[i] = nums[i] + *ms.rbegin();
ms.insert(dp[i]);
}
return dp.front();
// time : O(NlogK)
// space : O(N + K)
}
};
```
因為是slind window maximum可以使用deque
```cpp=
class Solution {
public:
int maxResult(vector<int>& nums, int k) {
vector<int> dp(nums.size());
dp.back() = nums.back();
deque<int> q{(int)nums.size() - 1};
for(int i = nums.size() - 2; i >= 0; --i) {
while(!q.empty() && q.front() > i + k) q.pop_front();
dp[i] = dp[q.front()] + nums[i];
while(!q.empty() && dp[i] > dp[q.back()]) q.pop_back();
q.push_back(i);
}
return dp.front();
// time : O(N)
}
};
```
###### tags: `leetcode` `刷題`
Google Drive
Gist
Clipboard
Sign in with Wallet
