动态规划入门

1.什么是动态规划
动态规划是在前面已有答案的基础上向下递推的过程

动态规划算法的两种形式
上面已经知道动态规划算法的核心是记住已经求过的解，记住求解的方式有两种：①自顶向下的备忘录法 ②自底向上。
为了说明动态规划的这两种方法，举一个最简单的例子：求斐波拉契数列Fibonacci 。先看一下这个问题：
Fibonacci (n) = 1; n = 0

Fibonacci (n) = 1; n = 1

Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2)；

使用递归非常简单，但是用动态规划是怎么处理的呢

public static int Fibonacci(int n)
{
if(n<=0)
return n;
int []Memo=new int[n+1];
for(int i=0;i<=n;i++)
Memo[i]=-1;
return fib(n, Memo);
}
public static int fib(int n,int []Memo)
{

    if(Memo[n]!=-1)
        return Memo[n];
//如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。               
    if(n<=2)
        Memo[n]=1;

    else Memo[n]=fib( n-1,Memo)+fib(n-2,Memo);  

    return Memo[n];
}

---

作者：HankingHu
来源：CSDN
原文：https://blog.csdn.net/u013309870/article/details/75193592

②自底向上的动态规划
备忘录法还是利用了递归，上面算法不管怎样，计算fib（6）的时候最后还是要计算出fib（1），fib（2），fib（3）……,那么何不先计算出fib（1），fib（2），fib（3）……,呢？这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。

public static int fib(int n)
{
if(n<=0)
return n;
int []Memo=new int[n+1];
Memo[0]=0;
Memo[1]=1;
for(int i=2;i<=n;i++)
{
Memo[i]=Memo[i-1]+Memo[i-2];
}
return Memo[n];
}

自底向上方法也是利用数组保存了先计算的值，为后面的调用服务。观察参与循环的只有 i，i-1 , i-2三项，因此该方法的空间可以进一步的压缩如下。

public static int fib(int n)
{
if(n<=1)
return n;

    int Memo_i_2=0;
    int Memo_i_1=1;
    int Memo_i=1;
    for(int i=2;i<=n;i++)
    {
        Memo_i=Memo_i_2+Memo_i_1;
        Memo_i_2=Memo_i_1;
        Memo_i_1=Memo_i;
    }       
    return Memo_i;
}

一般来说由于备忘录方式的动态规划方法使用了递归，递归的时候会产生额外的开销，使用自底向上的动态规划方法要比备忘录方法好。
你以为看懂了上面的例子就懂得了动态规划吗？那就too young too simple了。动态规划远远不止如此简单，下面先给出一个例子看看能否独立完成。然后再对动态规划的其他特性进行分析。

image.png
image.png
image.png
image.png
image.png
image.png

原文：https://blog.csdn.net/u013309870/article/details/75193592