动态规划

动态规划简介

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

动态规划五步曲

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

注：一些情况是递推公式决定了dp数组要如何初始化！

动态规划应该如何debug

当我们去学动态规划的题很容易出现看完题解，自己上手写代码一直通过不了，首先我们要明白，写动态规划，代码出问题很正常！

debug：

把dp数组打印出来，看看究竟是不是自己的思路所推演的结果

写动态规划最忌讳的就是不清楚dp数组的含义，不懂为什么这样初始化，只会一味的去背代码，要明白，不是所有的题都能凭借所谓的题感直接写出来的，我们得去明白其深层得含义，理解自己为什么要这样去操作。

我们在去写代码之前，一定要先把状态转移到dp数组上进行具体得模拟一遍，做到心里有数

通过不了时，请给自己发出以下三个疑问：

这道题目我举例推导状态转移公式了么？
我打印dp数组的日志了么？
打印出来了dp数组和我想的一样么？

通过上述文字，想必我们对动态规划已经有了初步得了解，那我们就来试试下面这道题目把！

小题一道

题目

斐波那契数，通常用F(n)表示，形成的序列称为 斐波那契数列 。该数列由0和1开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中n > 1给你n，请计算F(n)。
示例1

  • 输入：2
  • 输出：1
  • 解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例2

  • 输入：3
  • 输出：2
  • 解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例3

  • 输入：4
  • 输出：3
  • 解释：F(4) = F(3) + F(2) = 2 + 1 = 3

《代码随想录》算法公开课
力扣题目链接

思路

  1. 确定dp数组以及下标的含义
    dp[i]的定义为：第i个数的斐波那契数值是dp[i]
  2. 确定递推公式
    状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
  3. dp数组如何初始化
    题目已经告诉我们：dp[0]=0, dp[1]=1
  4. 确定遍历顺序
    从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
  5. 举例推导dp数组
    按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为8的时候，dp数组应该是如下的数列：0 1 1 2 3 5 8 13 21

注：如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

代码实现

完整dp解题代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int fib(int n) {
        if (n <= 1) return n;             
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int index = 2; index <= n; index++){
            dp[index] = dp[index - 1] + dp[index - 2];
        }
        return dp[n];
    }
}

简化后的dp解题代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 0;
        for (int i = 1; i < n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

递归解题代码

1
2
3
4
5
6
public class Solution{
    public int fib(int n){
        if(n < 2)return n;
        return fib(n-1) + fib(n-2);
    }
}