解题思路

• 这是一个“只能向前、每次采摘至多一次”的路径规划问题。由于走格子只会消耗苹果、采摘只会增加苹果，苹果数的峰值只可能出现在起点或某次采摘之后。

• 设苹果林为下标从 1 到 m 的数组 A[i]。从起点到第 i 格需消耗 i 个苹果；从已采摘的第 j 格走到更靠前的第 i 格需消耗 i-j 个苹果。到达时苹果可以为 0（但此时不能继续前进一步，正好在该格采摘）。

• 动态规划：

  • 定义 dp[t][i]：恰好进行了 t 次采摘且第 t 次在第 i 格后，采摘完成时手上的最大苹果数；不可达则为负无穷。
  • 初始转移（从起点直接到第 i 格并采摘一次）：若 n >= i，则 dp[1][i] = n - i + A[i]。
  • 一般转移（从已在 j 格完成第 t-1 次采摘的状态到 i 格进行第 t 次采摘）：