做网站靠广告一年赚多少钱/百度推广平台

递归和动态规划问题都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是：动态规划保存了子问题的解，避免重复计算。

爬楼梯：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

题解：定义一个数组dp存储上楼梯的方法数，dp[i]表示走到第i个楼梯的方法数。第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。

/*** */
package leetcode;import java.util.Scanner;/*** @author 李佳琪**/
public class Floor {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stubScanner scanner = new Scanner(System.in);while(scanner.hasNext()){int n = scanner.nextInt();int count = solve(n);System.out.println(count);}scanner.close();}public static int solve(int n){if(n==0){return 0;}if(n==1){return 1;}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];}}