动态规划 斐波那契数列_f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+p(n,m)}

Dynamic Programming

什么是动态规划？动态规划就是将一个大问题不断向下拆分成小问题，直到拆分出的小问题可以求出其解，然后将小问题的解不断的向上合并，最终得到大问题的解决方案。

动态规划三要素：

1.问题的阶段

2. 每个阶段的状态

3. 从前一个阶段转化到后一个阶段之间的递推关系

----递推关系必须是从次小的问题开始到较大的问题之间的转化

f(n,m)=max{f(n-1,m),f(n-1,m-w[n])+p(n,m)}

DP特性

• 重复子问题

• 无后效性（后面的依赖前面，但前面的不可依赖后面）

• 最优子结构

斐波那契数列

1 1 2 3 5 8 13 。。。

F(N)=F(N-1)+F(N-2)

F(1)=1 F(2)=1

递归写法

static int Fib(int n) {
 
    if(n==1 || n==2)
 
        return 1;
 
    else return Fib(n-1)+Fib(n-2);
 
}

递归写法存在很多重复计算，可以考虑用一个数组保存之前的计算结果--》

递归DP: （从后往前计算）

int[] arr=new int[N+1];
 
static int Fib(int n) {
 
    if(arr[n]>0)
 
        return arr[n];//大于0表示这个值已经计算过，直接返回
    
    if(n=