首页 > 百度笔试 (9.3) java 开发 --> 第三题:爬楼梯
头像
小饭盆
编辑于 2020-09-08 20:39
+ 关注

百度笔试 (9.3) java 开发 --> 第三题:爬楼梯

考试没做出来..
今天又想了一下,贴个答案,大佬们看看有没有问题

题目:
有n个台阶,每次至少走一个,但是要求每步和之前两步走的台阶数目不能一样,请问有多少种不同的解法,答案对10^9+7取模。
m > 2 && n >= m

9.8 更正 ,感谢楼下牛友(hhcsdxgt)的测试
原题解状态转移为“ dp[i+cur][cur][j] += 1 ”,更正为“ dp[i + cur][cur][j] += dp[i][j][k]  ”

public class Baidu {
	public static void main(String[] args) {
		// 测试, m>2 且 n > m
		int n = 1000;
		int m = 100;

		/*
		 * 定义:
		 * dp[i][j][k]: 前一次用j步,前前次用k步,到达第i个台阶的不同走法
		 * 		i -> {0..n}
		 * 		j -> {1..m}
		 * 		k -> {0..m}  考虑前前次用可能用了0步,比如:dp[1][1][0] = 1
		 * 
		 * 初始化:dp[q][q][0] = 1    
		 * 		q -> {1..m}
		 * 
		 * 目标:SUM(dp[n][j][k]) 
		 * 		j -> {1..m} 
		 * 		k -> {0..m}
		 * 
		 * 状态转移:
		 * 		对于dp[i][j][k],	
		 * 			如果  dp[i][j][k] != 0
		 * 				下一步为cur, 且满足:cur != j  && cur != k, 其中 cur -> {1..m}
		 * 				那么:dp[i + cur][cur][j] += dp[i][j][k]  * 			其他情况:
		 * 				dp[i+cur][cur][j] = 0
		 * 		
		 */
		
		int[][][] dp = new int[n+1][m+1][m+1];
		
		// 初始化
		for(int i = 1; i <= m; i++) {
			dp[i][i][0] = 1;
		}
		
		// 状态转移
		for(int i = 1; i <= n; i ++) {
			for(int j = 1; j <= m; j++) {
				for(int k = 0; k <= m; k++) {
					// 不满足条件
					if(k == j || i < j || i < k || dp[i][j][k] == 0) {
						continue;
					}
					for(int cur = 1; cur <= m; cur++) {
						// 不满足条件
						if(cur == j || cur == k || cur + i > n) {
							continue;
						}
						// 满足条件
						dp[i + cur][cur][j] += dp[i][j][k];
						dp[i + cur][cur][j] %= 1000000007;
					}
				}
			}
		}
		int ans = 0;
		// 求和 dp[n][j][k]
		for(int j = 1; j <= m; j++) {
			for(int k = 0; k <= m; k++) {
				if(k == j) {
					continue;
				}
				ans += dp[n][j][k];
				ans %= 1000000007;
			}
		}
		System.out.println(ans);
	}
}


全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐