Problems
LeetCode : 416. Partition Equal Subset Sum
[Knapsack Problem]
LeetCode : 718. Maximum Length of Repeated Subarray
LeetCode : 53. Maximum Subarray
LeetCode : 1937. Maximum Number of Points with Cost
LeetCode : 975. Odd Even Jump
[dynamic programming][red-black tree]
LeetCode : 2304. Minimum Path Cost in a Grid
[dynamic programming]
LeetCode : 2100. Find Good Days to Rob the Bank
[dynamic programming]
LeetCode : 2212. Maximum Points in an Archery Competition
[dynamic programming][0–1 Knapsack]
LeetCode : 2266. Count Number of Texts
[dynamic programming][string]
LeetCode : 2140. Solving Questions With Brainpower
[dynamic programming][array]
LeetCode : 1770. Maximum Score from Performing Multiplication Operations
[Dynamic Programming][Array]
LeetCode : 2435. Paths in Matrix Whose Sum Is Divisible by K
[Dynamic Programming]
LeetCode : 1578. Minimum Time to Make Rope Colorful
[Dynamic Programming][Greedy]
LeetCode : 2431. Maximize Total Tastiness of Purchased Fruits
[Dynamic Programming][0–1 knapsack]
LeetCode : 1463. Cherry Pickup II
[Dynamic Programming][Hard]
LeetCode : 2501. Longest Square Streak in an Array
[Dynamic Programming]
—
LeetCode : 474. Ones and Zeroes
geeksforgeeks : 0–1 Knapsack Problem
[Knapsack Problem]
LeetCode : 1049. Last Stone Weight II
[Knapsack Problem]
LeetCode : 42. Trapping Rain Water
LeetCode : 121. Best Time to Buy and Sell Stock
LeetCode : 312. Burst Balloons
LeetCode : 887. Super Egg Drop
LeetCode : 1884. Egg Drop With 2 Eggs and N Floors
LeetCode : 416. Partition Equal Subset Sum
1. 算出輸入陣列總和，並將其除以二
2. 令重量 == val，且背包大小為陣列總和 / 2 的值
3. 做 0/1 背包問題，並看是否能使取得的值 == 背包大小
class Solution {
public:
int dfsDp(int n, int capacity, vector<vector<int>> &dp, vector<int> &nums) {
if(n == 0) {
return 0;
}
if(capacity < 0) {
return 0;
}
if(dp[n][capacity] != -1) {
return dp[n][capacity];
}
if(capacity - nums[n - 1] >= 0) {
dp[n][capacity] = dfsDp(n - 1, capacity - nums[n - 1], dp, nums) + nums[n - 1];
}
dp[n][capacity] = max(dp[n][capacity], dfsDp(n - 1, capacity, dp, nums));
return dp[n][capacity];
}
bool canPartition(vector<int>& nums) {
int sum = 0;
for(int i = 0;i < nums.size();i++) {
sum += nums[i];
}
if(sum % 2 != 0) {
return false;
}
// 背包容量
sum /= 2;
// 01 背包問題的 dp
vector<vector<int>> dp = vector<vector<int>>(nums.size() + 1,
vector<int>(sum + 1, -1));
int res = dfsDp(nums.size(), sum, dp, nums);
return res == sum;
}
};LeetCode : 718. Maximum Length of Repeated Subarray
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int maxlen = 0;
vector<vector<int>> dp(A.size(), vector<int>(B.size(), 0));
// dp[i][j] means :
// maximum length of common suffix end at index i and j
for(int i = 0;i < A.size();i++) {
if(A[i] == B[0]) {
dp[i][0] = 1;
if(dp[i][0] > maxlen) {
maxlen = 1;
}
}
}
for(int i = 0;i < B.size();i++) {
if(A[0] == B[i]) {
dp[0][i] = 1;
if(dp[0][i] > maxlen) {
maxlen = 1;
}
}
}
for(int i = 1;i < A.size();i++) {
for(int j = 1;j < B.size();j++) {
if(A[i] == B[j]) {
dp[i][j] = dp[i-1][j-1] + 1;
if(dp[i][j] > maxlen) {
maxlen = dp[i][j];
}
}
}
}
return maxlen;
}
};LeetCode : 322. Coin Change
class Solution {
public:
int dfsDp(int amount, vector<int> &dp, vector<int> &coins) {
if(amount < 0) {
return INT_MAX;
} else if(amount == 0) {
return 0;
} else if(dp[amount] != -1) {
return dp[amount];
}
int minVal = INT_MAX;
for(int i = 0;i < coins.size();i++) {
int tmp = dfsDp(amount - coins[i], dp, coins);
minVal = min(minVal, tmp == INT_MAX ? INT_MAX : tmp + 1);
}
dp[amount] = minVal;
return dp[amount];
}
int coinChange(vector<int>& coins, int amount) {
if(0 == amount) {
return 0;
}
vector<int> dp = vector<int>(amount + 1, -1);
return dfsDp(amount, dp, coins) == INT_MAX ? -1 : dp[amount];
}
};LeetCode : 53. Maximum Subarray
假如當前的 sum 小於 0 ， 則該值加上下一個值的總和絕對會小於下一個值，所以當 sum < 0 ，就可以將該 sum 丟棄掉了。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxVal = INT_MIN;
int sum = 0;
for(int i = 0;i < nums.size();i++) {
sum += nums[i];
maxVal = max(maxVal, sum);
if(sum < 0) {
sum = 0;
}
}
return maxVal;
}
};LeetCode : 1937. Maximum Number of Points with Cost
這題看完別人的解釋才恍然大悟。
原本要 O ( N ) 的時間才能取得一格的解。使用 left[], right[] 去紀錄後，只需要 O ( 1 ) 的時間
#define LL long longclass Solution {
public:
void getRow(int r, vector<vector<LL>> &record, vector<vector<int>>& points) {
vector<LL> left = vector<LL>(record[0].size());
vector<LL> right = vector<LL>(record[0].size());
int maxVal = 0;
left[0] = record[r - 1][0];
for(int i = 1;i < points[0].size();i++) {
left[i] = max(left[i - 1] - 1, (LL)record[r - 1][i]);
}
right[points[0].size() - 1] = record[r - 1][points[0].size() - 1];
for(int i = record[0].size() - 2;i >= 0;i--) {
right[i] = max(right[i + 1] - 1, (LL)record[r - 1][i]);
}
for(int i = 0;i < record[0].size();i++) {
record[r][i] = max(left[i], right[i]) + points[r][i];
}
}
long long maxPoints(vector<vector<int>>& points) {
LL res = 0;
vector<vector<LL>> record = vector<vector<LL>>(points.size(), vector<LL>(points[0].size(), 0));
for(int i = 0;i < points[0].size();i++) {
record[0][i] = points[0][i];
}
for(int i = 1;i < points.size();i++) {
getRow(i, record, points);
}
for(int i = 0;i < points[0].size();i++) {
res = max(res, record.back()[i]);
}
return res;
}
};
LeetCode : 818. Race Car
/*
dp[2(direction)][log_2(speed)][position]
*/typedef struct Node Node;
struct Node {
int direction;
int speed;
int position;
int step;
};class Solution {
public:
int racecar(int target) {
vector<vector<vector<int>>> dp = vector<vector<vector<int>>>(2, vector<vector<int>>(16, vector<int>(target * 3, -1)));queue<Node> q;
q.push({0, 0, 0, 0});
dp[0][0][0] = 0;
while(!q.empty()) {
Node nown = q.front();
q.pop();
int nowd = nown.direction;
int nowsp = nown.speed;
int nowp = nown.position;
int nowst = nown.step;
int newd;
int newsp;
int newp;
int newst;
// 'A'
newd = nowd;
newsp = nowsp + 1;
if(newd == 0) {
newp = (nowp + pow(2, nowsp));
} else if(newd == 1) {
newp = (nowp - pow(2, nowsp));
}
newst = nowst + 1;
if(newp == target) {
return nowst + 1;
}
if(newsp < 16 &&
newp >= 0 && newp < target * 3 &&
dp[newd][newsp][newp] == -1) {
dp[newd][newsp][newp] = newst;
// printf("newd : %d, newsp : %d, newp : %d, newst : %d\n", newd, newsp, newp, newst);
q.push({newd, newsp, newp, newst});
}
// 'R'
newd = nowd ^ 1;
newsp = 0;
newp = nowp;
newst = nowst + 1;
if(newsp < 16 &&
newp >= 0 && newp < target * 3 &&
dp[newd][newsp][newp] == -1) {
dp[newd][newsp][newp] = newst;
// printf("newd : %d, newsp : %d, newp : %d, newst : %d\n", newd, newsp, newp, newst);
q.push({newd, newsp, newp, newst});
}
}
return 0;
}
};
LeetCode : 975. Odd Even Jump
class Solution {
public:
// jmp == 0 --> odd jmp
// jmp == 1 --> even jmp
bool dfs(int index, int jmp, vector<vector<int>> &dp, vector<vector<int>> &rec) {
if(-1 == index) {
return false;
}
if(dp.size() - 1 == index) {
return true;
}
if(0 != dp[index][jmp]) {
return 1 == dp[index][jmp] ? true : false;
}
if(dfs(rec[index][jmp], jmp ^ 1, dp, rec)) {
dp[index][jmp] = 1;
return true;
} else {
dp[index][jmp] = -1;
}
return false;
}
int oddEvenJumps(vector<int>& arr) {
vector<vector<int>> rec = vector<vector<int>>(arr.size(), vector<int>(2, -1));
vector<vector<int>> dp = vector<vector<int>>(arr.size(), vector<int>(2, 0));
rec.back()[0] = arr.size() - 1; // 當我們在該點，需要進行 odd jump 時
rec.back()[1] = arr.size() - 1; // 當我們在該點，需要進行 even jump 時
dp.back()[0] = arr.size() - 1; // 當我們在該點，需要進行 odd jump 時
dp.back()[1] = arr.size() - 1; // 當我們在該點，需要進行 even jump 時
// 用 map 去記錄所有走過的元素，以及其 index
// 處理 odd jmp 時， map 需要由小排到大
// 處理 even jmp 時，map 需要由大排到小
// lower_bound 找不到就讓它是 -1
// 最後再用 DFS 去構造 DP
int nowv;
int nowi;
// odd jmp
nowv = arr.back();
nowi = arr.size() - 1;
map<int, int> oddTmp;
oddTmp[100000] = -1; // upper bound
oddTmp[nowv] = nowi;
for(int i = arr.size() - 2;i >= 0;i--) {
auto it = oddTmp.lower_bound(arr[i]);
if(100000 == it->first) {
rec[i][0] = -1;
} else {
rec[i][0] = it->second;
}
oddTmp[arr[i]] = i;
}
// even jmp
nowv = arr.back();
nowi = arr.size() - 1;
map<int, int, greater<int>> evenTmp;
evenTmp[-1] = -1; // upper bound
evenTmp[nowv] = nowi;
for(int i = arr.size() - 2;i >= 0;i--) {
auto it = evenTmp.lower_bound(arr[i]);
if(-1 == it->first) {
rec[i][1] = -1;
} else {
rec[i][1] = it->second;
}
evenTmp[arr[i]] = i;
}
int res = 0;
for(int i = 0;i < arr.size();i++) {
if(dfs(i, 0, dp, rec)) {
res++;
}
}
return res;
}
};LeetCode : 2304. Minimum Path Cost in a Grid
class Solution {
public:
int dfs(int x, int y, vector<vector<int>>& grid, vector<vector<int>>& moveCost, vector<vector<int>> &dp) {
if(INT_MAX != dp[x][y]) {
return dp[x][y];
}
if(x == grid.size() - 1) {
dp[x][y] = grid[x][y];
return dp[x][y];
}
int minVal = INT_MAX;
for(int i = 0;i < grid[0].size();i++) {
minVal = min(minVal, dfs(x + 1, i, grid, moveCost, dp) + moveCost[grid[x][y]][i] + grid[x][y]);
}
dp[x][y] = minVal;
return dp[x][y];
}
int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
vector<vector<int>> dp = vector<vector<int>>(grid.size(), vector<int>(grid[0].size(), INT_MAX));
int minVal = INT_MAX;
for(int i = 0;i < grid[0].size();i++) {
dfs(0, i, grid, moveCost, dp);
minVal = min(minVal, dp[0][i]);
}
return minVal;
}
};LeetCode : 2100. Find Good Days to Rob the Bank
// TODO : 太慢了
class Solution {
public:
vector<int> goodDaysToRobBank(vector<int>& security, int time) {
vector<int> &se = security;
vector<int> noni = vector<int>(se.size(), 0); // non-increasing
vector<int> nond = vector<int>(se.size(), 0); // non-dcreasing
noni[0] = 1;
for(int i = 1;i < se.size();i++) {
if(se[i] <= se[i - 1]) {
noni[i] = noni[i - 1] + 1;
} else {
noni[i] = 1;
}
}
nond.back() = 1;
for(int i = se.size() - 2;i >= 0;i--) {
if(se[i] <= se[i + 1]) {
nond[i] = nond[i + 1] + 1;
} else {
nond[i] = 1;
}
}
vector<int> ans;
for(int i = 0;i < se.size();i++) {
if(noni[i] > time && nond[i] > time) {
ans.push_back(i);
}
}
return ans;
}
};LeetCode : 2212. Maximum Points in an Archery Competition
// 0-1 背包typedef struct Node Node;
struct Node {
int val;
bool shoot;
};class Solution {
public:
int dfs(int nowi, int nown, vector<vector<Node>> &dp, vector<int> &cost) {
if(nowi < 0 || nown < 0) {
return 0;
}
if(-1 != dp[nowi][nown].val) {
return dp[nowi][nown].val;
}
int t1 = 0;
if(nown >= cost[nowi]) {
t1 = dfs(nowi - 1, nown - cost[nowi], dp, cost) + nowi;
} else {
}
int t2 = dfs(nowi - 1, nown, dp, cost);
if(t1 > t2) {
dp[nowi][nown].val = t1;
dp[nowi][nown].shoot = true;
} else {
dp[nowi][nown].val = t2;
dp[nowi][nown].shoot = false;
}
return dp[nowi][nown].val;
}
vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) {
vector<int> bob = vector<int>(aliceArrows.size(), 0);
vector<vector<Node>> dp = vector<vector<Node>>(12, vector<Node>(numArrows + 1, {-1, false}));
vector<int> cost = aliceArrows;
for(int i = 0;i < cost.size();i++) {
cost[i]++;
}
dfs(11, numArrows, dp, cost);
int tmp = numArrows;
int tmpUsed = 0;
for(int i = 11;i >= 0;i--) {
if(dp[i][tmp].shoot) {
bob[i] = cost[i];
tmp -= cost[i];
tmpUsed += cost[i];
} else {
bob[i] = 0;
}
}
if(tmpUsed < numArrows) {
bob[0] = numArrows - tmpUsed;
}
return bob;
}
};
LeetCode : 2266. Count Number of Texts
// TODO : 效能太差
typedef struct Node Node;
struct Node {
char c;
int n;
};class Solution {
public:
int dfs_dp3(int nowi, vector<int> &dp3) {
if(nowi <= 0) {
return 0;
}
if(-1 != dp3[nowi]) {
return dp3[nowi];
}
dp3[nowi] = 0;
for(int i = 1;i <= 3;i++) {
dp3[nowi] += dfs_dp3(nowi - i, dp3);
dp3[nowi] %= 1000000007;
}
return dp3[nowi];
}
int dfs_dp4(int nowi, vector<int> &dp4) {
if(nowi <= 0) {
return 0;
}
if(-1 != dp4[nowi]) {
return dp4[nowi];
}
dp4[nowi] = 0;
for(int i = 1;i <= 4;i++) {
dp4[nowi] += dfs_dp4(nowi - i, dp4);
dp4[nowi] %= 1000000007;
}
return dp4[nowi];
}
int countTexts(string pressedKeys) {
vector<int> dp3 = vector<int>(max((int)pressedKeys.size() + 1, 4), -1);
vector<int> dp4 = vector<int>(max((int)pressedKeys.size() + 1, 5), -1);
vector<int> num = vector<int>(10, -1);
num[2] = 3;
num[3] = 3;
num[4] = 3;
num[5] = 3;
num[6] = 3;
num[7] = 4;
num[8] = 3;
num[9] = 4;
dp3[1] = 1;
dp3[2] = 2;
dp3[3] = 4;
dp4[1] = 1;
dp4[2] = 2;
dp4[3] = 4;
dp4[4] = 8;
dfs_dp3(pressedKeys.size(), dp3);
dfs_dp4(pressedKeys.size(), dp4);
vector<int> val;
char nowc = pressedKeys[0];
int nown = 1;
for(int i = 1;i < pressedKeys.size();i++) {
if(pressedKeys[i] == nowc) {
nown++;
} else {
if(3 == num[nowc - '0']) {
val.push_back(dp3[nown]);
} else if(4 == num[nowc - '0']) {
val.push_back(dp4[nown]);
}
nowc = pressedKeys[i];
nown = 1;
}
}
if(3 == num[nowc - '0']) {
val.push_back(dp3[nown]);
} else if(4 == num[nowc - '0']) {
val.push_back(dp4[nown]);
}
long long ans = 1;
for(int i = 0;i < val.size();i++) {
ans *= val[i];
ans %= 1000000007;
}
return ans;
}
};
LeetCode : 2140. Solving Questions With Brainpower
#define LL long long
class Solution {
public:
LL dfs(int nowi, vector<LL> &dp, vector<vector<int>>& questions) {
if(nowi >= dp.size()) {
return 0;
}
if(-1 != dp[nowi]) {
return dp[nowi];
}
LL t1 = dfs(nowi + 1, dp, questions);
LL t2 = dfs(nowi + questions[nowi][1] + 1, dp, questions) +
questions[nowi][0];
dp[nowi] = max(t1, t2);
return dp[nowi];
}
long long mostPoints(vector<vector<int>>& questions) {
vector<LL> dp = vector<LL>(questions.size(), -1);
dfs(0, dp, questions);
return dp[0];
}
};LeetCode : 1770. Maximum Score from Performing Multiplication Operations
// TODO : 效能太差
// 蠻喜歡這題的，原本用 unordered_map 會 TLE，
// 後來加上 diff 以及用二維陣列取代 unordered_map，就可以 pass 了
class Solution {
public:
int times = 0;
int dfs(int left, int right, int mi, vector<int> &nums, vector<int> &multi, vector<vector<int>> &dp, int diff) {
times++;
//printf("left : %d, right : %d, mi : %d\n", left, right, mi);
if(left > right || mi >= multi.size()) {
return 0;
} else if(dp[left][right - diff] != INT_MIN) {
return dp[left][right - diff];
}
int t1 = dfs(left + 1, right, mi + 1, nums, multi, dp, diff) + nums[left] * multi[mi];
int t2 = INT_MIN;
if(left != right) {
t2 = dfs(left, right - 1, mi + 1, nums, multi, dp, diff) + nums[right] * multi[mi];
}
dp[left][right - diff] = max(t1, t2);
return dp[left][right - diff];
}
int maximumScore(vector<int>& nums, vector<int>& multipliers) {
vector<vector<int>> dp = vector<vector<int>>(multipliers.size(), vector<int>(multipliers.size(), INT_MIN));
int diff = nums.size() - multipliers.size();
int ans = dfs(0, nums.size() - 1, 0, nums, multipliers, dp, diff);
return ans;
}
};LeetCode : 2435. Paths in Matrix Whose Sum Is Divisible by K
// TODO : 效能太差了
// 餘數的可能性最多為 50 種
#define MOD (1000000007)class Solution {
public:
int numberOfPaths(vector<vector<int>>& grid, int k) {
vector<vector<vector<int>>> tbl = vector<vector<vector<int>>>(grid.size(), vector<vector<int>>(grid[0].size(), vector<int>(k, 0)));
tbl[0][0][grid[0][0] % k]++;
for(int i = 0;i < grid.size();i++) {
for(int j = 0;j < grid[0].size();j++) {
int upx = i - 1;
int upy = j;
int leftx = i;
int lefty = j - 1;
if(upx >= 0) {
for(int q = 0;q < k;q++) {
if(tbl[upx][upy][q] > 0) {
int nextv = (q + grid[i][j]) % k;
tbl[i][j][nextv] += tbl[upx][upy][q];
tbl[i][j][nextv] %= MOD;
}
}
}
if(lefty >= 0) {
for(int q = 0;q < k;q++) {
if(tbl[leftx][lefty][q] > 0) {
int nextv = (q + grid[i][j]) % k;
tbl[i][j][nextv] += tbl[leftx][lefty][q];
tbl[i][j][nextv] %= MOD;
}
}
}
}
}
return tbl.back().back()[0];
}
};
LeetCode : 1578. Minimum Time to Make Rope Colorful
class Solution {
public:
/*
int state[s.size()][2];
state[i][0] --> 這個字母沒被刪掉的 cost，這個字母一定要被刪，這裡就給一個誇張大的值
state[i][1] --> 這個字母被刪掉的 cost ， 不需要刪，就給一個誇張大的值
state[i][2] --> 這個字母被刪掉的話，就存上一個字母。上一個字母在邊界，就給 -1。上一個字母不需要刪，就給 -1
*/
int minCost(string s, vector<int>& cost) {
vector<int> temp;
int ans = 0;
char nowc = s[0];
temp.push_back(cost[0]);
for(int i = 1;i < s.size();i++) {
if(s[i] == nowc) {
temp.push_back(cost[i]);
} else {
if(temp.size() > 1) {
sort(temp.begin(), temp.end());
for(int i = 0;i < temp.size() - 1;i++) {
ans += temp[i];
}
}
temp.clear();
temp.push_back(cost[i]);
nowc = s[i];
}
}
if(temp.size() > 1) {
sort(temp.begin(), temp.end());
for(int i = 0;i < temp.size() - 1;i++) {
ans += temp[i];
}
}
return ans;
}
};LeetCode : 2431. Maximize Total Tastiness of Purchased Fruits
// 01 背包
class Solution {
public:
int dfs(int nowi, int nowc, int nowa, vector<vector<vector<int>>> &dp, vector<int>& price, vector<int>& tastiness) {
if(nowc < 0 || nowa < 0) {
return INT_MIN;
}
if(nowi < 0) {
return 0;
}
if(dp[nowi][nowc][nowa] != -1) {
return dp[nowi][nowc][nowa];
}
int maxVal = 0;
// 不買當前的水果
maxVal = max(maxVal, dfs(nowi - 1, nowc, nowa, dp, price, tastiness));
// 買當前水果
maxVal = max(maxVal, dfs(nowi - 1, nowc, nowa - price[nowi], dp, price, tastiness) + tastiness[nowi]);
// 買當前水果且使用折價券
maxVal = max(maxVal, dfs(nowi - 1, nowc - 1, nowa - price[nowi] / 2, dp, price, tastiness) + tastiness[nowi]);
dp[nowi][nowc][nowa] = maxVal;
return maxVal;
}
int maxTastiness(vector<int>& price, vector<int>& tastiness, int maxAmount, int maxCoupons) {
vector<vector<vector<int>>> dp = vector<vector<vector<int>>>(price.size(), vector<vector<int>>(maxCoupons + 1, vector<int>(maxAmount + 1, -1)));
// dp[i][j][k]
// i : 第幾件物品
// j : 還有幾個 coupon
// k : 剩下多少錢
dfs(price.size() - 1, maxCoupons, maxAmount, dp, price, tastiness);
return dp[price.size() - 1][maxCoupons][maxAmount];
}
};LeetCode : 1463. Cherry Pickup II
/*
想法 1 : brute force
robot 1 先走一步，再來是 robot 2 走一步
接下來換 robot 1 走一步
每個 robot 都走遍所有的三種可能
*/
/*
想法 2 : brute force
robot 1 先走到底，再換 robot 2 走
*/
/*
dp[row][col of robot1][col of robot2]
--> dfs
最多需要試 70 * 70 * 70
*/
class Solution {
public:
int dfs(int row, int col1, int col2, vector<vector<vector<int>>> &dp, vector<vector<int>>& grid) {
if(col1 < 0 || col2 < 0 ||
col1 >= grid[0].size() ||
col2 >= grid[0].size()) {
return -1;
}
if(dp[row][col1][col2] != -1) {
return dp[row][col1][col2];
}
if(row == grid.size() - 1) {
if(col1 == col2) {
dp[row][col1][col2] = grid[row][col1];
} else {
dp[row][col1][col2] = grid[row][col1] + grid[row][col2];
}
return dp[row][col1][col2];
}
int tmp;
if(col1 == col2) {
tmp = grid[row][col1];
} else {
tmp = grid[row][col1] + grid[row][col2];
}
int tmp2 = -1;
tmp2 = max(tmp2, dfs(row + 1, col1 + 1, col2, dp, grid));
tmp2 = max(tmp2, dfs(row + 1, col1 - 1, col2, dp, grid));
tmp2 = max(tmp2, dfs(row + 1, col1, col2, dp, grid));
tmp2 = max(tmp2, dfs(row + 1, col1 + 1, col2 - 1, dp, grid));
tmp2 = max(tmp2, dfs(row + 1, col1 - 1, col2 - 1, dp, grid));
tmp2 = max(tmp2, dfs(row + 1, col1, col2 - 1, dp, grid));
tmp2 = max(tmp2, dfs(row + 1, col1 + 1, col2 + 1, dp, grid));
tmp2 = max(tmp2, dfs(row + 1, col1 - 1, col2 + 1, dp, grid));
tmp2 = max(tmp2, dfs(row + 1, col1, col2 + 1, dp, grid));
dp[row][col1][col2] = tmp2 + tmp;
return dp[row][col1][col2];
}
int cherryPickup(vector<vector<int>>& grid) {
vector<vector<vector<int>>> dp = vector<vector<vector<int>>>(grid.size(), vector<vector<int>>(grid[0].size(), vector<int>(grid[0].size(), -1)));
return dfs(0, 0, grid[0].size() - 1, dp, grid);;
}
};
LeetCode : 2501. Longest Square Streak in an Array
// TODO : 效能太差
class Solution {
private:
int limit;
public:
int dfs(int nowi, unordered_map<int, int> &um, vector<int> &v, vector<int> &dp) {
int val = v[nowi];
if(dp[nowi] != INT_MIN) {
return dp[nowi];
}
if(val > limit) {
dp[nowi] = 1;
return 1;
}
int goal = val * val;
if(um.find(goal) != um.end()) {
dp[nowi] = dfs(um[goal], um, v, dp) + 1;
} else {
dp[nowi] = 1;
return 1;
}
return dp[nowi];
}
int longestSquareStreak(vector<int>& nums) {
unordered_map<int, int> um;
vector<int> v;
vector<int> dp;
int maxVal = INT_MIN;
limit = sqrt(INT_MAX);
// 這步是為了去除重複的元素
// 可能不需要這一步會比較快？
for(int i = 0;i < nums.size();i++) {
if(um.find(nums[i]) == um.end()) {
v.push_back(nums[i]);
um[nums[i]] = 1;
}
}
dp = vector<int>(v.size(), INT_MIN);
um.clear();
sort(v.begin(), v.end());
for(int i = 0;i < v.size();i++) {
um[v[i]] = i;
}
for(int i = 0;i < v.size();i++) {
maxVal = max(maxVal, dfs(i, um, v, dp));
}
return maxVal == 1 ? -1 : maxVal;
}
};