思路
动态规划。
状态定义
dp[i][j] 表示前 i 篇分享,第 i 篇分享的点赞量为 j 的情况下,有多少种不同方案数。
状态转移
题目描述
小红写了 n 篇题解,编号从 1 到 n,但是小红忘了每篇题解有多少人点赞了。
现在他有如下两种信息:
- 每篇题解的点赞量都为正数,且不超过 m。
- 第 i 篇题解的点赞量和第 i+1 篇题解的点赞量的大小关系。
在这些信息的条件下,所有题解的点赞量一共有多少种不同可能(答案对 109+7 取模)?
输入描述
第一行为两个正整数 n,m(1≤n,m≤2000),分别表示小红的题解数量 n,以及每篇题解的点赞量的上限 m。
第二行为一个长度为 n−1 的字符串 s,只包括 '>'
、'<'
、'='
三种字符:
- 如果 s[i]=′>′,则第 i 篇题解的点赞量严格大于第 i+1 篇题解的点赞量。
- 如果 s[i]=′<′,则第 i 篇题解的点赞量严格小于第 i+1 篇题解的点赞量。
- 如果 s[i]=′=′,则第 i 篇题解的点赞量等于第 i+1 篇题解的点赞量。
输出描述
输出一个整数表示所有题解的点赞量一共有多少种不同可能(答案对 109+7 取模)。
样例输入 1
4 3
<=>
样例输出 1
5
样例输入 2
4 3
>>>
样例输出 2
0