题目链接:
题解
动态规划,定义 dp[n][2][3]
,分别代表长度为 n,包含几个 A,末尾有几个 L 的方案数,转移的时候仔细点就可以。
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
class Solution { public: int checkRecord(int n) { long long dp[123456][2][3]; int mod = 1e9+7; memset(dp, 0, sizeof dp); dp[0][0][0] = 1; for (int i=1;i<=n;i++) { dp[i][0][0] = (dp[i][0][0] + dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2])%mod;
dp[i][0][1] = (dp[i][0][1] + dp[i-1][0][0])%mod;
dp[i][0][2] = (dp[i][0][2] + dp[i-1][0][1])%mod;
dp[i][1][0] = (dp[i][1][0] + dp[i-1][1][0] + dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]+ dp[i-1][1][1] + dp[i-1][1][2])%mod;
dp[i][1][1] = (dp[i][1][1] + dp[i-1][1][0])%mod;
dp[i][1][2] = (dp[i][1][2] + dp[i-1][1][1])%mod;
} long long ans = 0; for (int i=0;i<2;i++) { for(int j=0;j<3;j++) { ans = (ans + dp[n][i][j]) % mod; } } return ans % mod; } };
|