变态跳台阶_JAVA_简单
变态跳台阶
http://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387
- 设跳上n阶台阶的次数为f(n),跳上n阶台阶可以转换为最后一步上台阶,两步上台阶...n步上台阶,即为f(n) = S(n - 1)
- 转换:
由 f(n) = S(n - 1)
则 f(n) = S(n - 1) = f(n - 1) + S(n - 2) = 2f(n - 1)
public class Solution { public int JumpFloorII(int target) { if(target <= 1) return 1; // f(n) = 2f(n - 1) return (int)Math.pow(2,target - 1); } }