场景题:给定一个 m 行 n 列的棋盘,每个格子有一个数值,你有 k 把钥匙,每把钥匙可以解锁一个格子。解锁规则:每次解锁必须使用一把钥匙;新解锁的格子的值必须大于之前所有已解锁格子的值;新解锁的格子必须位于上一个已解锁格子的右下方(即行、列坐标都不小于上一个格子,允许同行或同列)。求总共有多少种不同的解锁序列。
考察说明
考察动态规划与组合计数,以及在二维有序约束下的序列计数能力
回答思路
- 能准确建模状态:以最后一个解锁格子和已解锁数量为状态
- 能按值的大小排序并利用坐标单调性设计转移
- 能处理值相等时的非严格/严格大小关系与坐标约束
- 能正确编写动态规划或计数状态转移并处理边界和取模