这一道题的递推式推出来不难。首先，在后面加一个数字就只能是奇数或者偶数。那我们设想一下，如果前一位是2，那后一位也得是2。因此，递推数组只需加一即可。而如果前一位是奇数，那么后一位就能取1和3。也就是f[i] = f[i - 1] - 1（剪掉全是2的填法）* 2 + 1(加上全是2的填法)。代码如下：

#include <iostream> using namespace std; int main(){ long long n,a[51] = {1,5}; cin >> n; for(int i = 2;i < n;i ++){ a[i] = a[i - 1] * 2 - 1; } cout << a[n - 1]; return 0; }

本质上只是2的格子数次方+1，因为全是二只有一种情况，每个都是奇数时每个格子有两种情况，记2^n次

题目思路（DP） 相邻两格的和为偶数 ⇔ 两格同奇偶性。 可填数字只有 1, 2, 3： * 奇数：1, 3（2 个选择） * 偶数：2（1 个选择） 因此一旦第 1 格确定了奇偶性，后面所有格子的奇偶性都被固定（必须全部同奇或全偶）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 动态规划写法 设： * odd[i]：前 i 个格子填完，且第 i 个格子是奇数的方案数 * even[i]：前 i 个格子填完，且第 i 个格子是偶数的方案数 转移（相邻必须同奇偶）： * odd[i] = odd[i-1] * 2（第 i 格是奇数，有 1 或 3 两种） * even[i] = even[i-1] * 1（第 i 格是偶数，只能填 2） 初始化： * odd[1] = 2 * even[1] = 1 答案： * odd[n] + even[n] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 普通数组 C++ 代码 > n ≤ 50，结果最大是 2^50 + 1，用 unsigned long long 足够。

#include <bits/stdc++.h> using namespace std; long long n,f[55]; int main(){ cin>>n; f[1]=3; f[2]=5; f[3]=9; for(int i=4;i<=n;i++){ f[i]=f[i-1]*2-1; } cout<<f[n]; return 0; }

#include<bits/stdc++.h> using namespace std; long long p[1005]; int main(){ long long n; cin >> n; p[1] = 1; p[2] = 5; p[3] = 9; for(int i = 4;i <= n;i++) p[i] = p[i-1] * 2 - 1; cout << p[n]; return 0; }