作者主页：Designer 小郑 作者简介：Java全栈软件工程师一枚，来自浙江宁波，负责开发管理公司OA项目，专注软件前后端开发（Vue、SpringBoot和微信小程序）、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师，全栈领域优质创作者，在校期间参加PAT乙级考试获得满分，三年ACM竞赛经验，斩获国奖两项，省奖五项。热爱技术、专注业务、开放合作、乐于分享，期待你我共同成长！ 主打方向：Vue、SpringBoot、微信小程序
题目链接：题目链接
题面：
小王在体验 “飞机大战” 后，将自己送到了太空。突然，小王失去了重力，在空中停了下来！
没等小王反应过来，一座闪闪发光的天桥映入小王的眼帘，这是一座长度为 N（0 <= N <= 200000) 的天桥，即小王当前位置和终点之间有 N 个踏板。
每个踏板上由三个子踏板，分别为 J 、Q 、K，腿短的小王无法跨越多个踏板，即每个踏板必须踏一次，每次必须选择踏板中的某个子踏板（J、Q、K之一），如下图所示。
这个天桥踏板还有一个特殊机制，如果小王连续脚踏三段不一致的子踏板，小王就会坠落，掉入无限深渊！
比如经过长度为 3 的天桥，小王可以选择依次踏 JJJ 或 JQJ，然后安全到达终点。
如果小王依次踏 JQK 或 KQJ，就会坠落。
小王想知道，自己安全到达天桥终点的踏法有几种？
本题需要你至少了解一些 Java 中数组的使用，了解递推的演算方式，为了降低时间复杂度，建议您采用打表的求解方式。
引用说明：上面的图片来源于蓝桥云课。
知识点
- Java 数组基本语法
- 递推运算
- 打表
初始代码
代码语言：javascript复制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)，需要注意必须打表，否则会超时。
参考代码如下。
参考代码如下：
代码语言：javascript复制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 本题，必须学会递推的算法，找到递推数组的关系公式，并需要预先打表降低时间复杂度，最终通过本题。
