【每日算法Day 95】美团笔试题:四面体方案个数

今天就更新一道刚做的美团在线编程题吧。

题目描述

一个四面体,顶点为 S, A, B, C。从 S 出发,每次任意选一条棱走到另一个顶点,可重复走过所有顶点和棱。问走 $k$ 次之后,回到 S 的方案数是多少?答案对 $1e9+7$ 取模。

题解

明显这是一道动态规划题目,我们令 $dp[i][0]$ 表示走了 $i$ 次之后回到 S 的方案数,令 $dp[i][1]$ 表示走了 $i$ 次之后在 $A, B, C$ 的概率。注意到这里 A, B, C 是对称的,所以方案数应该完全相同,所以我们定义一个就行了。

那么 $i$ 步回到 S 的方案数应该就是 $i-1$ 步在 A, B, C 的方案数之和:
$$
dp[i][0] = dp[i-1][1] * 3
$$

$i$ 步在 A 的方案数就是 $i-1$ 步在 B, C 的方案数加上 $i-1$ 步在 S 的方案数:
$$
dp[i][1] = dp[i-1][1] * 2 + dp[i-1][0]
$$

当然空间还可以优化,因为只跟上一步有关,所以保存上一步两个状态值就行了。

代码

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;
}

   转载规则


《【每日算法Day 95】美团笔试题:四面体方案个数》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【每日算法Day 96】腾讯面试题:合并两个有序数组 【每日算法Day 96】腾讯面试题:合并两个有序数组
昨天腾讯一面上来就给我整的这道 easy 难度的题,然后我太紧张了还想了一会儿,差点炸裂。 题目链接LeetCode 88. 合并两个有序数组 题目描述给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 num
2020-04-10
下一篇 
【每日算法Day 94】经典面试题:机器人的运动范围 【每日算法Day 94】经典面试题:机器人的运动范围
最近在忙面试,本来今天都不想更了,但是看基础知识看的太累了,于是写道题排解一下压力。 题目链接LeetCode 面试题13. 机器人的运动范围 题目描述地上有一个 m 行 n 列的方格,从坐标 [0, 0] 到坐标 [m-1, n-1]
2020-04-08
  目录