Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間4月前 (2025/08/08 01:26)推噓2(2推 0噓 0→)

3363. 不懂這題為什麼能算hard == 原本以為會重疊超麻煩結果發現根本就直接切開算就好真的會重疊的話要問走到邊不是走到角落 class Solution { public: int maxCollectedFruits(vector<vector<int>>& f) { int n = f.size(); int res = 0; //(0, 0) for(int i = 0; i < n; i++){ res += f[i][i]; } //top right int half = n / 2; vector<int> dp(n, 0); int i = 0; for(; i < half; i++){ vector<int> next(n, 0); for(int j = 0; j <= i; j++){ next[j] = f[i][n-1-j]; int add = dp[j]; if(j > 0) add = max(add, dp[j-1]); if(j < i) add = max(add, dp[j+1]); next[j] += add; } dp = move(next); } if(n % 2 == 0) half--; for(; i < n-1; i++, half--){ vector<int> next(n, 0); for(int j = 0; j < half; j++){ next[j] = f[i][n-1-j]; int add = dp[j]; if(j > 0) add = max(add, dp[j-1]); if(j < half) add = max(add, dp[j+1]); next[j] += add; } dp = move(next); } res += dp[0]; //button left half = n / 2; dp = vector<int>(n, 0); int j = 0; for(; j < half; j++){ vector<int> next(n, 0); for(int i = 0; i <= j; i++){ next[i] = f[n-1-i][j]; int add = dp[i]; if(i > 0) add = max(add, dp[i-1]); if(i < j) add = max(add, dp[i+1]); next[i] += add; } dp = move(next); } if(n % 2 == 0) half--; for(; j < n-1; j++, half--){ vector<int> next(n, 0); for(int i = 0; i < half; i++){ next[i] = f[n-1-i][j]; int add = dp[i]; if(i > 0) add = max(add, dp[i-1]); if(i < half) add = max(add, dp[i+1]); next[i] += add; } dp = move(next); } res += dp[0]; return res; } }; -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg