Re: [閒聊] 每日leetcode

[sixB (6B)]

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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.99.218 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1754587618.A.ECC.html
推 Sougou: 太卷了吧
推 oin1104: 我好崇拜你