题目描述：
蒜头君觉得白色的墙面好单调，他决定给房间的墙面涂上颜色。他买了 3 种颜料分别是红、黄、蓝，然后把房间的墙壁竖直地划分成 n 个部分，蒜头希望每个相邻的部分颜色不能相同。他想知道一共有多少种给房间上色的方案。 例如，当 n=5 时，下面就是一种合法方案。 |蓝|红|黄|红|黄| 由于墙壁是一个环形，所以下面这个方案就是不合法的。 |蓝|红|黄|红|黄|蓝| 输入格式 一个整数 n，表示房间被划分成多少部分。（1≤n≤50） 输出格式 一个整数，表示给墙壁涂色的合法方案数。 样例输入 4 样例输出 18
解题思路： 注意：dp[i]代表一共有i个部分的墙，一共有几个方案去给墙涂颜色 （1）首先给dp数组初始化，比如有1部分的墙时的方案数，有2个部分的墙的方案数，有3个部分的墙的方案数。dp[1]=3,dp[2]=6,dp[3]=6; （2）找出递推式：dp[i]=dp[i-1]+2*dp[i-2];
对于（2）的解释如下： 一共有i个部分的墙 ①第i-1个部分的墙和第1部分的墙颜色不同，（这个时候第i个部分的墙既不能和第1个部分的墙颜色一样，也不能和第i-1个部分的墙颜色一样），所以第i个部分的墙的颜色已然确定，只有一种，所以dp[i]=dp[i-1]； ②第i-1个部分的墙和第1部分的墙颜色相同，（这个时候第i-2个部分的墙不能和第1以及第i-1个部分的墙颜色一样），所以第i个部分的墙的颜色有两种dp[i]=2dp[i-2]；【注意：在dii-2个部分的墙的颜色确定的情况下，第i个部分的墙的颜色有两种方案，所以最终的结果是2dp[i-2]】 所以，dp[i]=dp[i-1]+2dp[i-2];
AC代码：
#include <stdlib.h> #include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> #include <math.h> using namespace std; long long dp[55]; int main() { int i,n; cin>>n; // dp[i]:一共有i个部分的墙，一共有几个方案去给墙涂颜色 dp[1]=3; dp[2]=6; dp[3]=6; for(i=4;i<=n;i++) dp[i]=dp[i-1]+2*dp[i-2]; cout<<dp[n]<<endl; return 0; }