动态规划涉及的问题类型太多太多，写这篇blog简要的介绍一下动态规划系列中经典的几个问题，帮助读者快速的入门。

1.递归函数时间复杂度计算

递归函数调用的次数(递归树上节点的个数,每个节点代表一次递归调用)×递归函数本身的复杂度

2.剑指Offer 10-1.斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1
示例 2：

输入：n = 5
输出：5

提示：

0 <= n <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
非典型的动态规划问题，但是可以用动态规划的思想来解决
状态转移方程（递推公式）：f(n)=f(n-1)+f(n-2)

自顶向下

  • 暴力递归(此方法在测试数据43时会超出时间限制)

    1. class Solution {
    2.   static int mod=(int)1e9+7;
    3.   public int fib(int n) {
    4.       if(n<=1)return n;
    5.       return ((fib(n-1))%mod+(fib(n-2))%mod)%mod;
    6.   }
    7. }

  • 备忘录递归

我们在该题的递归树中可以看出，很多数值被重复计算，为了提高我们代码运行的效率，我们可以适当剪枝：也就是说，我们建立一个备忘录memo来记录该元素是否被计算过，如果被计算过，则continue。
image.png
转载自:labuladong(https://www.bilibili.com/video/BV1XV411Y7oE?from=search&seid=7761246862475240872&spm_id_from=333.337.0.0)

  1. class Solution {
  2.     static int mod=(int)1e9+7;
  3.     public int fib(int n) {
  4.         int[] memo=new int[n+1];
  5.         return ans_fib(memo,n);
  6.     }
  8.     private static int ans_fib(int[] memo,int N){
  9.         if(N<=1)return N;
  10.         if(memo[N]!=0){
  11.             return memo[N];
  12.         }
  13.         memo[N]=((ans_fib(memo,N-1))%mod+(ans_fib(memo,N-2))%mod)%mod;
  14.         return memo[N];
  15.     }
  16. }

自底向上

  • dp数组的迭代解法
    1. class Solution {
    2.   static int mod=(int)1e9+7;
    3.   public int fib(int n) {
    4.       if(n==0)   return 0;
    5.       int[] dp=new int[n+1];
    6.       dp[0]=0;
    7.       dp[1]=1;
    8.       for(int i=2;i<dp.length;i++){
    9.           dp[i]=((dp[i-1])%mod+(dp[i-2])%mod)%mod;
    10.       }
    11.       return dp[n];
    12.   }
    13. }

    3.剑指Offer II 103.最少的硬币数量

    给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0
示例 4：

输入：coins = [1], amount = 1
输出：1
示例 5：

输入：coins = [1], amount = 2
输出：2

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gaM7Ch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  • 备忘录解法

    1. class Solution {
    2.   public int coinChange(int[] coins, int amount) {
    3.       int[] memo=new int[amount+1];
    4.       Arrays.fill(memo,-6);
    5.       return dp(memo,coins,amount);
    6.   }
    8.   private static int dp(int[] memo,int[] coins,int n){
    9.       if(n==0) return 0;
    10.       if(n<0) return -1;
    11.       if(memo[n]!=-6)
    12.           return memo[n];
    13.       int min=Integer.MAX_VALUE;
    14.       for(int coin:coins){
    15.           int ans=dp(memo,coins,n-coin);
    16.           if(ans==-1)
    17.               continue;
    18.           min=Math.min(min,ans+1);
    19.       }
    20.       memo[n]=min==Integer.MAX_VALUE?-1:min;
    21.       return memo[n];
    22.   }
    23. }

  • 自底向上的动态规划解法

    1. class Solution {
    2.   public int coinChange(int[] coins, int amount) {
    3.       //自底向上的动态规划解法
    4.       int[] dp=new int[amount+1];
    5.       Arrays.fill(dp,amount+1);
    6.       dp[0]=0;
    7.       for(int i=0;i<dp.length;i++){
    8.           for(int coin:coins){
    9.               if((i-coin)<0){
    10.                   continue;
    11.               }
    12.               dp[i]=Math.min(dp[i],1+dp[i-coin]);
    13.           }
    14.       }
    15.       return dp[amount]==amount+1?-1:dp[amount];
    16.   }
    17. }

    4.leetcode.70 爬楼梯

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

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

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

提示：

1 <= n <= 45

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路和算法

我们用 f(x)表示爬到第 xx级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：

f(x) = f(x - 1) + f(x - 2)

  • 备忘录解法

    1. class Solution {
    2.   static int[] memo;
    3.   public int climbStairs(int n) {
    4.       //备忘录技巧
    5.       memo=new int[n+1];
    6.       memo[1]=1;
    7.       Arrays.fill(memo,0);
    8.       return climb(n);
    9.   }
    11.   private static int climb(int N){
    12.       if(N<=2) return N;
    13.       if(memo[N]!=0){
    14.           return memo[N];
    15.       }
    16.       memo[N]=climb(N-1)+climb(N-2);
    17.       return memo[N];
    18.   }
    19. }