1463.摘櫻桃II

方法：動態規劃（遞推）

昨天是摘櫻桃I，今天是II，與昨天的區別主要在于，今天的是兩個人分別從左上角和右上角出發，且只能往下或右下和左下移動，求都移動到最后一排所能摘到櫻桃的數量。

直接附上題解吧：
作者：靈茶山艾府
鏈接：https://leetcode.cn/problems/cherry-pickup-ii/solutions/2768158/jiao-ni-yi-bu-bu-si-kao-dpcong-ji-yi-hua-i70v/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

class Solution {public int cherryPickup(int[][] grid) {int m = grid.length;int n = grid[0].length;int[][][] f = new int[m + 1][n + 2][n + 2];for (int i = m - 1; i >= 0; i -- ) {for (int j = 0; j < Math.min(n, i + 1); j ++ ) {for (int k = Math.max(j + 1, n - 1 - i); k < n; k ++ ) {f[i][j + 1][k + 1] = max(f[i + 1][j][k], f[i + 1][j][k + 1], f[i + 1][j][k + 2],f[i + 1][j + 1][k], f[i + 1][j + 1][k + 1], f[i + 1][j + 1][k + 2],f[i + 1][j + 2][k], f[i + 1][j + 2][k + 1], f[i + 1][j + 2][k + 2]) + grid[i][j] + grid[i][k];}}}return f[0][1][n];}private int max(int x, int... y) {for (int v : y) {x = Math.max(x, v);}return x;}
}

時間復雜度：
O(nm²)

空間復雜度：
O(nm²)