如何求解递推问题

1. 确定递推状态（重点）

   一个函数符号f(x)，外加这个函数符号的含义描述 一般函数所对应的值，就是要求解的值

2. 确定递推公式（)

   确定f(x)究竟依赖于哪些f(y)的值

3. 分析边界条件

4. 程序实现

   递归 || 循环

案例分析

(1)环形墙上色

题目

给一个环形的墙图颜色，一共三种颜色，分别是红、黄、蓝，墙壁被竖直地划分成n个部分，相邻的部分颜色不能相同。请问一下总共有多少种给房间上色的方案。

样例

例如当n=5时，下面是一种合法方案

由于墙壁是环形的，下面的方案就不合法

分析

1. 确定递推状态

代表前n块墙壁，在不考虑头尾成环的前提下，第1块涂颜色，第色涂颜色的方法总数。

1. 确定递推公式

1. 递推的初始值

1. 最终答案

优化

考虑到第一块涂蓝色和涂红色的方案数量是一样的，可以给第一块直接涂第0种颜色，最后一块涂第j种颜色，这就设置了一个隐变量。

1. 确定递推状态
   代表前n块墙壁，在不考虑头尾成环的前提下，第1块涂颜色，第色涂颜色的方法总数。
2. 确定递推公式
   
3. 递推的初始值
   
4. 最终答案
   

   再优化

:::info 可以看出来确定递推状态是最重要的，它影响后续所有步骤 :::