LeetCode 每日一题 ---- 【741.摘樱桃】

741.摘樱桃

方法：动态规划

这是一道动态规划的题目，enmmmm，依旧是做不出来，尤其是看到困难两个标红的字体，就更不想做了，然后是看着答案一点一点顺着思路和题解做的，做完后发现也没有想象中的那么难

从(n-1, n-1)返回(0, 0)可以等价的看做又一次从(0, 0)到(n-1, n-1)的路径，
然后求一个所能采到樱桃个数的最大值
不妨假设两人同时出发，且速度相同。无论这两人怎么走，在时间相同的情况下，
他们向右走的步数加上向下走的步数之和是一个定值（设为 k）。
设两人的坐标为 (x1,y1)和 (x2,y2)，则 x1+y1=x2+y2=k。
那么当 x1=x2 时，必然有 y1=y2，即两个人到达了同一个格子。
定义状态：f[k][x1][x2]
k表示两个人分别从(x1, k - x1)和(x2, k - x2)同时触发，到达(n-1, n-1)锁摘到樱桃个数之和
x1，x2分别代表第一个和第二个人的起始横坐标
状态转移方程：
f[k][x1][x2]可以由四种情况转移过来
都往右：f[k][x1][x2] = f[k-1][x1][x2]
A往下，B往右：f[k][x1][x2] = f[k-1][x1-2][x2]
A往右，B往下：f[k][x1][x2] = f[k-1][x1][x2-1]
都往下：f[k][x1][x2] = f[k-1][x1-1][x2-1]
f[k][x1][x2]的最终结果是上述四种情况的最大值，然后再累加上grid[x1][k-x1]和grid[x2][k-x2]就可以得到最终该位置的答案
若x1==x2说明第一个人和第二个人的位置重合了，所以在这种情况下，grid[x1][k-x1]只能加一次

/**
从(n-1, n-1)返回(0, 0)可以等价的看做又一次从(0, 0)到(n-1, n-1)的路径，
然后求一个所能采到樱桃个数的最大值
不妨假设两人同时出发，且速度相同。无论这两人怎么走，在时间相同的情况下，
他们向右走的步数加上向下走的步数之和是一个定值（设为 k）。
设两人的坐标为 (x1,y1)和 (x2,y2)，则 x1+y1=x2+y2=k。
那么当 x1=x2 时，必然有 y1=y2，即两个人到达了同一个格子。
定义状态：f[k][x1][x2] k表示两个人分别从(x1, k - x1)和(x2, k - x2)同时触发，到达(n-1, n-1)锁摘到樱桃个数之和x1，x2分别代表第一个和第二个人的起始横坐标
状态转移方程：f[k][x1][x2]可以由四种情况转移过来都往右：f[k][x1][x2] = f[k-1][x1][x2]A往下，B往右：f[k][x1][x2] = f[k-1][x1-2][x2]A往右，B往下：f[k][x1][x2] = f[k-1][x1][x2-1]都往下：f[k][x1][x2] = f[k-1][x1-1][x2-1]f[k][x1][x2]的最终结果是上述四种情况的最大值，然后再累加上grid[x1][k-x1]和grid[x2][k-x2]就可以得到最终该位置的答案若x1==x2说明第一个人和第二个人的位置重合了，所以在这种情况下，grid[x1][k-x1]只能加一次*/
class Solution {public int cherryPickup(int[][] grid) {int n = grid.length;int[][][] f = new int[n * 2 - 1][n][n];// 初始化for (int i = 0; i < n * 2 - 1; i ++ ) {for (int j = 0; j < n; j ++ ) {Arrays.fill(f[i][j], Integer.MIN_VALUE);}}f[0][0][0] = grid[0][0];for (int k = 1; k < n * 2 - 1; k ++ ) {// 防止越界for (int x1 = Math.max(k - n + 1, 0); x1 <= Math.min(k, n - 1); x1 ++ ) {int y1 = k - x1;// 荆棘不可越过if (grid[x1][y1] == -1) {continue;}for (int x2 = x1; x2 <= Math.min(k, n - 1); x2 ++ ) {int y2 = k - x2;if (grid[x2][y2] == -1) {continue;}// 都往右int res = f[k - 1][x1][x2];// 往下，往右if (x1 > 0) {res = Math.max(res, f[k - 1][x1 - 1][x2]);}// 往右，往下if (x2 > 0) {res = Math.max(res, f[k - 1][x1][x2 - 1]);}// 都往下if (x1 > 0 && x2 > 0) {res = Math.max(res, f[k - 1][x1 - 1][x2 - 1]);}res += grid[x1][y1];if (x2 != x1) {res += grid[x2][y2];}f[k][x1][x2] = res;}}}return Math.max(f[n * 2 - 2][n - 1][n - 1], 0);}
}

时间复杂度：
O(n³)

空间复杂度：
O(n²)