今天就更新一道刚做的美团在线编程题吧。
题目描述
一个四面体，顶点为 S, A, B, C。从 S 出发，每次任意选一条棱走到另一个顶点，可重复走过所有顶点和棱。问走 次之后，回到 S 的方案数是多少？答案对 取模。
题解
明显这是一道动态规划题目，我们令 表示走了 次之后回到 S 的方案数，令 表示走了 次之后在 的概率。注意到这里 A, B, C 是对称的，所以方案数应该完全相同，所以我们定义一个就行了。
那么 步回到 S 的方案数应该就是 步在 A, B, C 的方案数之和：
步在 A 的方案数就是 步在 B, C 的方案数加上 步在 S 的方案数：
当然空间还可以优化，因为只跟上一步有关，所以保存上一步两个状态值就行了。
代码
c++
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int N = 1000010; ll dp[N][2]; int main() { int k; scanf("%d", &k); memset(dp, 0, sizeof dp); dp[0][0] = 1; for (int i = 1; i <= k; ++i) { dp[i][0] = (dp[i-1][1] * 3) % mod; dp[i][1] = (dp[i-1][1] * 2 + dp[i-1][0]) % mod; } printf("%lld\n", dp[k][0]); return 0; }
空间优化（c++）
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int N = 1000010; ll dp[2]; int main() { int k; scanf("%d", &k); dp[0] = 1; dp[1] = 0; for (int i = 1; i <= k; ++i) { int a = (dp[1] * 3) % mod; int b = (dp[1] * 2 + dp[0]) % mod; dp[0] = a; dp[1] = b; } printf("%lld\n", dp[0]); return 0; }
