# Leetcode 1463. Cherry Pickup II
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/cherry-pickup-ii/submissions/ 。

想法 :

HARD不愧是HARD，DEBUG到我要尖叫了，最後參考別人的CODE才發現是我第一列的狀態轉移寫錯了・・・

這題想法沒有很難，就是爬梯子的三維版，陣列代表的狀態是現在兩個機器人所在的位置(列、行、行)。
轉移的時候要特別判斷兩個機器人有沒有位於同一Column。

時間複雜度 : O(n*m^2)

程式碼 :

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int r=grid.size(), c=grid[0].size(), dp[100][100][100]={0}, dir[3]={-1,0,1}, ans;

        for(int i=0 ; i<r ; i++){
            for(int j=0 ; j<c ; j++){
                for(int k=0 ; k<c ; k++){
                    dp[i][j][k] = -1;
                }
            }
        }
        
        ans=dp[0][0][c-1]=grid[0][0]+grid[0][c-1];
        
        
        for(int i=1 ; i<r ; i++){
            for(int j=0 ; j<c ; j++){
                for(int k=0 ; k<c ; k++){
                    int prev=dp[i-1][j][k];
                 
                    if(prev >= 0){
                    
                        for(int m=0 ; m<3 ; m++){
                        int c1=j+dir[m];
                            
                        for(int n=0 ; n<3 ; n++){
                                int c2=k+dir[n];

                                if(c1 >= 0 && c1 < c && c2 >= 0 && c2 < c){    
                                    if(c1 == c2) dp[i][c1][c2] = max(dp[i][c1][c2], prev + grid[i][c1]);
                                    else dp[i][c1][c2] = max(dp[i][c1][c2], prev + grid[i][c1] + grid[i][c2]);            

                                    ans=max(ans,dp[i][c1][c2]);
                                }
                            }
                        }
                    }
                }
            }
        }
        
        return ans;
    }
};