动态规划dp（三个案例详解）

一、对于dp的理解：

dp（Dynamic programming）即动态规划的简写。动态规划的思想是找出大问题对应的子问题，通过若干子问题寻找解决这个大问题的递推公式或者方法的思想即大化小，小化更小。例如求第n个斐波那契数就需要求出n-1与n-2的斐波那契数字往前一步一步推导出第n个数。

二、寻找的三个指标

1. 定义状态（f（n）表示什么）
2. 寻找转移方程（f（n）= xx  xx）
3. 设置初始值（f（0）=  x ，f（1） =  y）

通过这三个指标就可以一步步得到f(n)的值。

三、三个例子

1、斐波那契

       在数学上，斐波纳契数列以如下递归方式被定义：F(0)=1 , F(1)=1 , … , F(n)=F(n-1)+F(n-2)（n≥2，n∈N+）根据定义，其前十项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55。给出一个编程问题：输入一个自然数n，要求输出斐波那契数列的第（0≤n≤1000000）。

我们先找出这个问题的三个指标

思路：每一个斐波那契数字都等于前两个数字的和。

• 定义状态                 f(n) 表示第n个斐波那契数;
• 寻找转移方程         f(n) = f(n-1) + f(n-2);
• 设置初始值             f(0) = 1 , f(1) = 1;

public int Fibonacci(int n)
{
  if(n==0 || n==1) return 1;
  else return Fibonacci(n-1)+Fibonacci(n-2);
}

2、青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

我们先找出这个问题的三个指标

思路：将跳台阶问题反过来看，看最后一个台阶的跳法：倒数第一个台阶的跳法（最后跳一步）+倒数第二个台阶的跳法（最后直接跳两步。分别跳两步倍包含在跳倒数最后一个的跳法里了）。

• 定义状态                f(n) 表示第n个台阶的跳法
• 寻找转移方程         f(n) = f(n-1) （倒数第一个台阶的跳法）+ f(n-2)（倒数第二个台阶的跳法）
• 设置初始值             f(0) = 1 , f(1) = 1 , f(2) = 2;

public int jumpFloor(int target) {
        int[] dp = new int[target+1];
        // 由于从0到1只有一种，而从0到2有0>1>1和0>2两种，初始化边界使之满足dp
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= target; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[target];
    }

四、放格子的问题

将n个21的方块放在大小为2n大小的格子内，求当长度为n时候放的方法有几种

我们先找出这个问题的三个指标

思路：最后的格子可以横着放2个方块或者竖着放一个，我们就求这两个方法的和就是总的放方块的方法数

• 定义状态                f(n) 表示长为n的方格放的方法
• 寻找转移方程         f(n) = f(n-1) + f(n-2)
• 设置初始值             f(0) = 1 , f(1) = 1 , f(2) = 2;

public int num(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }