---
# System prepended metadata

title: 1463. Cherry Pickup II
tags: [Leetcode, Dynamic Programming, Hard]

---

# 1463. Cherry Pickup II
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/cherry-pickup-ii/
## 思路
如果dp是2d的话 ```int[][] temp = dp.clone() temp``` 存的还是dp的指针 这时候就要一行一行copy
如果dp是1d的话就是不是copy指针了
```dp[i][j]```表示在当前行一个robot在```i```一个robot在```j```所能拥有的最大cherry数
```a=i-1/i/i+1 b=j-1/j/j+1``` 上一层的```dp[a][b]```可以到达```dp[i][j]``` 所以在这9种组合里面选最大的即可
## Code
```java=
class Solution {
    public int cherryPickup(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[n][n];
        for(int i=0; i<n; i++) Arrays.fill(dp[i], Integer.MIN_VALUE/2);
        dp[0][n-1] = grid[0][0]+grid[0][n-1];
        
        for(int row=1; row<m; row++){
            // temp = dp.clone() does not work for 2d array
            int[][] temp = new int[n][n];
            for(int i=0; i<n; i++) temp[i] = dp[i].clone();
            
            for(int i=0; i<n; i++){
                for(int j=i; j<n; j++){
                    dp[i][j] = Integer.MIN_VALUE/2;
                    for(int a=i-1; a<=i+1; a++){
                        if(a<0 || a>=n) continue;
                        for(int b=j-1; b<=j+1; b++){
                            if(b<0 || b>=n) continue;
                            if(i==j) dp[i][j] = Math.max(dp[i][j], temp[a][b]+grid[row][i]);
                            else dp[i][j] = Math.max(dp[i][j], temp[a][b]+grid[row][i]+grid[row][j]);
                        }
                    }
                }
            }
        }
        
        int ans = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
}
```