algorithm

动态规划

动态规划是一种 从底到顶 的方法 无需使用低柜。

/* 爬楼梯： 动态规划*/

package DP;

/* 爬楼梯文同*/
public class example1 {
public  static    int climbingStairsDp(int n){
        if (n == 1 || n== 2){
            return n;
        }
        //初始化DP表，用于存储子问题的解
        int[] dp = new int[n+1];
        //初始化状态，没有最小子问题的解
        dp[1] =1 ;
        dp[2] =2 ;
        // 从较小问题逐渐转移到较大问题
        for (int i = 3; i <= n ; i++) {
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int res =climbingStairsDp(3);
        System.out.println("res = " + res);
    }
}

空间优化版本如下
  /* 爬楼梯:空间优化后的动态规划 */ 
int climbingStairsDPComp(int n) {
if(n==1||n==2) return n;
inta=1,b=2; for(inti=3;i<=n;i++){
inttmp=b; b=a+b; a=tmp;
}
return b; }