LeetCode 每天练习 ---- 741 题摘樱桃

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

• 741.采摘樱桃
  • • 途径：采用动态规划策略

LeetCode 741题摘樱桃解析

动态规划方法应用

这是一道关于动态规划的题目，emmmmm，依旧难以解决，特别是看到“困难”两个字被标红后，更是不想继续思考了。后来只能通过查看答案，逐步顺着题解的思路进行理解，完成之后发现其实并没有想象中那么难。

从(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]可由以下四种情况转移而来：

第一种