动

态规划：

将原问题拆借位若干子问题，同时保存子问题的答案，是的每一个子问题只求解一次，最终获得原问题的答案

 

举个例子

爬楼梯问题

假设你正在爬楼梯。需要 n阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

使用递归的解决方式

static int climbStairs(int n){

if ( n==0){

return 0;

    }

if (n ==1){

return 1;

    }

return climbStairs(n-1)+climbStairs(n-2);

}

很明显这个方法的复杂度已经达到了指数级别。在递归过程中存在很多的重复计算 

利用动态规划解决问题

这里选用leetcode中的题目（10.Climbing Stairs）进行演示

有一个楼梯，总共有n阶台阶。每一次，可以上一个台阶，也可以上两个台阶。问，哦啊上这样的一个楼梯，一共有多少不同的方法。

-如n  = 3，可以爬上这个楼梯的方法有【1,1,1】，【1,2】 ，【2,1】

通过记忆优化进行搜索--自上而下的解决问题

自上而下的解决方式是相对会更加容易的，而自下而上思考问题是会更难的

private static int[]list;

static int fib(int n){

if ( n==0){

return 0;

    }

if (n ==1){

return 1;

    }

if (list[n] !=0) {

list[n] =fib(n-1)+fib(n-2);

    }

return list[n];

}

通过记忆优化进行搜索--自下而上的解决问题(这里因为题型的原因，所以自下而上并没有那么复杂)

private static int climbStairs(int n) {

    int[] arr = new int[n + 1];

    arr[0] = 1; arr[1] = 1; for (int i = 2; i <= n; i++) {

    arr[i] = arr[i-1] + arr[i-2];

    }

    return arr[n];

}

两者的主要区别在于一个是从头部开始计算，而另外一个从底部开始计算。

线性规划区别于递归函数的地方在于线性规划将每次函数调用的结果保存了起来，在下次调用之前先看是否已经存在

线性规划在时间上占优势，而递归在空间上占优势