Re: [閒聊] 每日LeetCode

※ 引述 《JIWP (神楽めあ的錢包)》 之銘言： : 　 : 1463 Cherry Pickup II : 　 : 給一個2維矩陣grid，grid[i][j]代表這個格子的櫻桃數量 : 　 : 有兩個機器人會收集格子上的櫻桃 : 　 : 當兩個機器人走到同一格的時候，只有一個機器人可以拿grid[i][j]個櫻桃，另一個拿0 個 : 　 : 機器人一個是從左上角grid[0][0]，另一個是從右上角grid[0][cols-1] : 　 : 每次可以往左下、正下、右下走 : 　 : 請問機器人最多可以收集幾個櫻桃 這題一開始蠻難想的 偷偷看了一下提示之後 哇幹 對欸 可以三維 姆咪 思路： 有圖應該就很好懂ㄌ https://i.imgur.com/nstwFsh.jpg 就跟下墜一樣 要把每一層的動作分開來討論 然後 要先知道某一層地方每一種走法的sum 所以會用paper來記錄他們 接下來就可以dp了 每一層都用sum來記錄走過的總和 然後兩個機器人都可以左右一格 所以sum在更新的時候要看自己的九宮格最大的 然後最後再看最後一層最大的就可以了 我beat 99.??% 媽的好爽 class Solution { public: int cherryPickup(vector<vector<int>>& grid) { int layer = grid.size(); int n = grid[0].size(); int paper[layer][n][n]; int sum[layer][n][n]; for(int l = 0 ; l < layer ; l ++) { for(int i = 0 ; i < n ; i ++) { for(int j = 0 ; j < n ; j ++) { if(i != j) { paper[l][i][j] = grid[l][i] + grid[l][j]; } else if(i == j) { paper[l][i][j] = grid[l][i]; } sum[l][i][j] = -1; } } } sum[0][n-1][0] = paper[0][n-1][0]; for(int l = 1 ; l < layer ; l ++) { for(int i = 0 ; i < n ; i ++) { for(int j = 0 ; j < n ; j ++) { int lastmax = -1; if((i-1>=0)&&(j-1>=0)) { lastmax = max(lastmax , sum[l-1][i-1][j-1]); } if((i-1>=0)) { lastmax = max(lastmax , sum[l-1][i-1][j]); } if((i-1>=0)&&(j+1<n)) { lastmax = max(lastmax , sum[l-1][i-1][j+1]); } if((j-1>=0)) { lastmax = max(lastmax , sum[l-1][i][j-1]); } lastmax = max(lastmax , sum[l-1][i][j]); if(j+1<n) { lastmax = max(lastmax , sum[l-1][i][j+1]); } if((i+1<n)&&(j-1>=0)) { lastmax = max(lastmax , sum[l-1][i+1][j-1]); } if((i+1<n)) { lastmax = max(lastmax , sum[l-1][i+1][j]); } if((i+1<n)&&(j+1<n)) { lastmax = max(lastmax , sum[l-1][i+1][j+1]); } if(lastmax!=-1) { sum[l][i][j] = lastmax + paper[l][i][j]; } } } } int ans = 0; for(int i = 0 ; i < n ; i ++) { for(int j = 0 ; j < n ; j ++) { ans = max(sum[layer-1][i][j] , ans); } } return ans; } }; -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.28.91 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707661899.A.FD4.html