# 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指针了

## Code

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;
    }
}