|
package com.algorithm.dynamicprogramming;
/**
?* 算法描述：有个N个台阶的楼梯，每次只能爬1个或者2个，请问有多少种爬法 Example 1:
?*?
?* Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1
?* step + 1 step 2. 2 steps
?*?
?* Example 2:
?*?
?* Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1.
?* 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step
?*?
?* @author rich
?*
?*/
public class ClimbingStairs {
?? ?public static void main(String[] args) {
?? ??? ?// 非记忆
?? ??? ?int n = 5;
?? ??? ?System.out.println(climbingStairsRecursion(n));
?? ??? ?System.out.println(climbingStairsLoop(n));
?? ??? ?// 记忆处理
?? ??? ?int[] memo = new int[n+1];
?? ??? ?System.out.println(climbingStairsRecursion(n,memo));
?? ??? ?
?? ?}
?? ?
?? ?/**
?? ? * 递归处理
?? ? * 算法分析：当n=1时，只有一种，
?? ? * 当n=2时，1+1和2两种，
?? ? * 当n=3时，1+1+1，2+1，1+2三种，
?? ? * 当n=4时，有1+1+1+1，2+1+1，2+2，1+1+2，1+2+1，共五种。
?? ? * 当n=5时，有1+1+1+1+1，2+1+1+1，2+2+1，1+2+1+1，1+2+2，1+1+2+1，1+1+1+2，2+1+2共八种
?? ? * 由上f(n) = f(n-1)+f(n-2) 同斐波那契数列类似
?? ? * @param n
?? ? * @return
?? ? */
?? ?public static int climbingStairsRecursion(int n) {
?? ??? ?if (n == 1) {
?? ??? ??? ?return 1;
?? ??? ?}
?? ??? ?if (n == 2) {
?? ??? ??? ?return 2;
?? ??? ?}
?? ??? ?return climbingStairsRecursion(n-1)+climbingStairsRecursion(n-2);
?? ?}
?? ?
?? ?/**
?? ? * 循环处理
?? ? * 算法分析：当n=1时，只有一种，
?? ? * 当n=2时，1+1和2两种，
?? ? * 当n=3时，1+1+1，2+1，1+2三种，
?? ? * 当n=4时，有1+1+1+1，2+1+1，2+2，1+1+2，1+2+1，共五种。
?? ? * 当n=5时，有1+1+1+1+1，2+1+1+1，2+2+1，1+2+1+1，1+2+2，1+1+2+1，1+1+1+2，2+1+2共八种
?? ? * 由上f(n) = f(n-1)+f(n-2) 同斐波那契数列类似
?? ? * @param n
?? ? * @return
?? ? */
?? ?public static int climbingStairsLoop(int n) {
?? ??? ?if (n == 1) {
?? ??? ??? ?return 1;
?? ??? ?}
?? ??? ?if (n == 2) {
?? ??? ??? ?return 2;
?? ??? ?}
?? ??? ?int[] memo = new int[n+1];
?? ??? ?memo[1] = 1;
?? ??? ?memo[2] = 2;
?? ??? ?for (int i = 3;i<=n;i++) {
?? ??? ??? ?memo[i] = memo[i-1] + memo[i-2];
?? ??? ?}
?? ??? ?return memo[n];
?? ?}
?? ?
?? ?/**
?? ? * 递归处理
?? ? * 算法分析：当n=1时，只有一种，
?? ? * 当n=2时，1+1和2两种，
?? ? * 当n=3时，1+1+1，2+1，1+2三种，
?? ? * 当n=4时，有1+1+1+1，2+1+1，2+2，1+1+2，1+2+1，共五种。
?? ? * 当n=5时，有1+1+1+1+1，2+1+1+1，2+2+1，1+2+1+1，1+2+2，1+1+2+1，1+1+1+2，2+1+2共八种
?? ? * 由上f(n) = f(n-1)+f(n-2) 同斐波那契数列类似
?? ? * @param n
?? ? * @return
?? ? */
?? ?public static int climbingStairsRecursion(int n,int[] memo) {
?? ??? ?if (n == 1) {
?? ??? ??? ?memo[1] = 1;
?? ??? ??? ?return 1;
?? ??? ?}
?? ??? ?if (n == 2) {
?? ??? ??? ?memo[1] = 2;
?? ??? ??? ?return 2;
?? ??? ?}
?? ??? ?int f1 = memo[n-1];
?? ??? ?if (f1 <= 0) {
?? ??? ??? ?f1 = climbingStairsRecursion(n-1);
?? ??? ??? ?memo[n-1] = f1;
?? ??? ?}
?? ??? ?int f2 = memo[n-2];
?? ??? ?if (f2 <= 0) {
?? ??? ??? ?f2 = climbingStairsRecursion(n-2);
?? ??? ??? ?memo[n-2] = f2;
?? ??? ?}
?? ??? ?return f1+f2;
?? ?}
}
?
|