【每日算法Day 95】美团笔试题：四面体方案个数
题目描述
一个四面体，顶点为 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;
}
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-04-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
