塔子哥的题解点赞方案-美团2023笔试(codefun2000)
题目链接
塔子哥的题解点赞方案-美团2023笔试(codefun2000)
题目内容
塔子哥写了 n 篇题解，编号从 1 到 n，但是塔子哥忘了每篇题解有多少人点赞了。
现在他有如下两种信息：
1、每篇题解的点赞量都为正数，且不超过 m。
2、第 i 篇题解的点赞量和第 i+1 篇题解的点赞量的大小关系。
在这些信息的条件下，所有题解的点赞量一共有多少种不同可能（答案对 1 0 9 + 7 10^9+7 109+7取模）
输入描述
输出描述
输出一个整数表示所有题解的点赞量一共有多少种不同可能（答案对 1 0 9 + 7 10^9+7 109+7取模）。
样例1
输入
4 3
<=>
输出
5
样例1解释
样例2
输入
4 3
>>>
输出
0
题解1
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9 +7;
const int N = 2005;int n, m;
LL dp[N][N]; // dp[i][j]表示第i题题解的点赞数不超过j的方案数
char s[N];int main(){scanf("%d%d", &n, &m);scanf(" %s", s + 1);for(int j = m; j > 0; j--) dp[n][j]=1;for(int i = n - 1; i > 0; i--){if(s[i] == '>'){for(int j = 1; j <= m; j++){dp[i][j] = (dp[i + 1][j - 1] + dp[i][j - 1]) % MOD; }}else if(s[i] == '='){for(int j = 1; j <= m; j++) {dp[i][j] = dp[i + 1][j];}}else {for(int j = m; j > 0; j--){dp[i][j] = (dp[i][j + 1] + dp[i + 1][j + 1]) % MOD;}}}LL ans = 0;for(int j = m; j > 0; j--){ans = (ans + dp[1][j]) % MOD;}printf("%lld\n", ans);return 0;
}