浙江省住房城乡建设厅官方网站,?a品定制网站开发,合肥建工学校,哈尔滨免费建站模板LeetCode 每日一题 ---- 【741.摘樱桃】 741.摘樱桃方法#xff1a;动态规划 741.摘樱桃
方法#xff1a;动态规划
这是一道动态规划的题目#xff0c;enmmmm#xff0c;依旧是做不出来#xff0c;尤其是看到困难两个标红的字体#xff0c;就更不想做了#xff0c;然后… LeetCode 每日一题 ---- 【741.摘樱桃】 741.摘樱桃方法动态规划 741.摘樱桃
方法动态规划
这是一道动态规划的题目enmmmm依旧是做不出来尤其是看到困难两个标红的字体就更不想做了然后是看着答案一点一点顺着思路和题解做的做完后发现也没有想象中的那么难
从(n-1, n-1)返回(0, 0)可以等价的看做又一次从(0, 0)到(n-1, n-1)的路径 然后求一个所能采到樱桃个数的最大值 不妨假设两人同时出发且速度相同。无论这两人怎么走在时间相同的情况下 他们向右走的步数加上向下走的步数之和是一个定值设为 k。 设两人的坐标为 (x1,y1)和 (x2,y2)则 x1y1x2y2k。 那么当 x1x2 时必然有 y1y2即两个人到达了同一个格子。 定义状态f[k][x1][x2] k表示两个人分别从(x1, k - x1)和(x2, k - x2)同时触发到达(n-1, n-1)锁摘到樱桃个数之和 x1x2分别代表第一个和第二个人的起始横坐标 状态转移方程 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]就可以得到最终该位置的答案 若x1x2说明第一个人和第二个人的位置重合了所以在这种情况下grid[x1][k-x1]只能加一次
/**
从(n-1, n-1)返回(0, 0)可以等价的看做又一次从(0, 0)到(n-1, n-1)的路径
然后求一个所能采到樱桃个数的最大值
不妨假设两人同时出发且速度相同。无论这两人怎么走在时间相同的情况下
他们向右走的步数加上向下走的步数之和是一个定值设为 k。
设两人的坐标为 (x1,y1)和 (x2,y2)则 x1y1x2y2k。
那么当 x1x2 时必然有 y1y2即两个人到达了同一个格子。
定义状态f[k][x1][x2] k表示两个人分别从(x1, k - x1)和(x2, k - x2)同时触发到达(n-1, n-1)锁摘到樱桃个数之和x1x2分别代表第一个和第二个人的起始横坐标
状态转移方程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]就可以得到最终该位置的答案若x1x2说明第一个人和第二个人的位置重合了所以在这种情况下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(n3)
空间复杂度 O(n2)
