LeetCode/Dpproblem.java at master · maskwang520/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package test;
/**
 * 青蛙跳阶梯问题，DP解决
 * @author maskwang
 *
 */
public class Dpproblem {
	static int sum = 0;
	static int num = 0;
//
//	public static int JumpFloor(int target) {
//		if (sum < target) {
//			for (int i = 1; i <= 2; i++) {
//				sum = sum + i;
//				JumpFloor(target);
//				sum = sum - i;
//			}
//		}
//		if (sum == target) {
//			num++;
//		}
//		return num;
//	}
	/**
	 * 简单的动态规划，状态转移方程f(n)=f(n-1)+f(n-2),n=1,n=2边界
	 * @param target
	 * @return
	 */
	public static int JumpFloor(int target) {
		if(target==0)
			return 0;
		if(target==1)
			return 1;
		if(target==2)
			return 2;
		int a=1,b=2,temp = 0;
		for(int i=3;i<=target;i++){
			temp=a+b;
			a=b;
			b=temp;
		}
		return temp;
	}

	public static void main(String[] args) {
		System.out.println(JumpFloor(4)) ;
	}

}