741. 摘樱桃 : 经典线性 DP 运用题

题目描述

这是 LeetCode 上的 741. 摘樱桃 ，难度为 困难。

Tag : 「线性 DP」

一个$N \times N$ 的网格( grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：

• $0$ 表示这个格子是空的，所以你可以穿过它。
• $1$ 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
• $-1$ 表示这个格子里有荆棘，挡着你的路。