题目链接：题目链接
题面：
小王在体验 “飞机大战” 后，将自己送到了太空。突然，小王失去了重力，在空中停了下来！
没等小王反应过来，一座闪闪发光的天桥映入小王的眼帘，这是一座长度为 N（0 <= N <= 200000) 的天桥，即小王当前位置和终点之间有 N 个踏板。
每个踏板上由三个子踏板，分别为 J 、Q 、K，腿短的小王无法跨越多个踏板，即每个踏板必须踏一次，每次必须选择踏板中的某个子踏板（J、Q、K之一），如下图所示。
这个天桥踏板还有一个特殊机制，如果小王连续脚踏三段不一致的子踏板，小王就会坠落，掉入无限深渊！
比如经过长度为 3 的天桥，小王可以选择依次踏 JJJ 或 JQJ，然后安全到达终点。
如果小王依次踏 JQK 或 KQJ，就会坠落。
小王想知道，自己安全到达天桥终点的踏法有几种？
本题需要你至少了解一些 Java 中数组的使用，了解递推的演算方式，为了降低时间复杂度，建议您采用打表的求解方式。
引用说明：上面的图片来源于蓝桥云课。
知识点
- Java 数组基本语法
- 递推运算
- 打表
初始代码
public class DMain { public static int doWork(int n) { int ans = 1; //代码编辑区 开始 //代码编辑区 结束 return ans; } public static void main(String[] args) { //测试用例 System.out.printf((Objects.equals(2048L,doWork(2)) ? "【√正确】" : "【X错误】") + "天桥长度 %d,通过方法为%d种\n",2,doWork(2)); } }
样例说明
输入天桥长度 N，输出安全到达天桥终点的踏法有几种。
如天桥长度 N = 2，则输出 9。
如天桥长度 N = 3，则输出 21。
题解
递推题，递推公式Fn(i) = 2 * Fn(i - 1) + Fn(i - 2)，需要注意必须打表，否则会超时。
参考代码如下。
参考代码如下：
import java.util.ArrayList; import java.util.List; import java.util.Objects; public class DAns { public static boolean INIT_FLAG = false; public static List<Integer> ANS_LIST; public static int doWork(int n) { int ans = 1; //代码编辑区 开始 if(!INIT_FLAG) { init(); } ans = ANS_LIST.get(n); //代码编辑区 结束 return ans; } private static void init() { ANS_LIST = new ArrayList<>(); ANS_LIST.add(0); ANS_LIST.add(3); ANS_LIST.add(9); for(int i = 3; i <= 100000; i ++) { ANS_LIST.add(2 * ANS_LIST.get(i - 1) + ANS_LIST.get(i - 2)); } INIT_FLAG = true; } public static void main(String[] args) { //测试用例 System.out.printf((Objects.equals(9,doWork(2)) ? "【√正确】" : "【X错误】") + "天桥长度 %d,通过方法为%d种\n",2,doWork(2)); System.out.printf((Objects.equals(21,doWork(3)) ? "【√正确】" : "【X错误】") + "天桥长度 %d,通过方法为%d种\n",3,doWork(3)); } private static int run(int n) { if(Objects.equals(1,n)) { return 3; } else if(Objects.equals(2,n)) { return 9; } else { return 2 * run(n - 1) + run(n - 2); } } }
总结
要 AC 本题，必须学会递推的算法，找到递推数组的关系公式，并需要预先打表降低时间复杂度，最终通过本题。
