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

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);
	}
}