C++算法学习心得八.动态规划算法（1）

1.动态规划理论基础

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

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

对于动态规划问题，拆解为如下五步曲，

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

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

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的。

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果 

发出这样的问题之前，其实可以自己先思考这三个问题：

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

 2.斐波那契数（508题）

题目描述：

斐波那契数，通常用 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

动规五部曲：

这里我们要用一个一维dp数组来保存递归的结果

1. 确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

1. 确定递推公式

为什么这是一道非常简单的入门题目呢？

因为题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

1. dp数组如何初始化

题目中把如何初始化也直接给我们了，如下：

dp[0] = 0;
dp[1] = 1;

1. 确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

1. 举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

class Solution {
public:
    int fib(int n) {
        if(n<=1)return n;//
        vector<int>dp(n+1);//定义一个动态规划数组，含义是第i个斐波那契数
        dp[0] = 0;//初始值设定
        dp[1] = 1;
        //遍历顺序，从前向后遍历
        for(int i = 2;i <= n;i++){
            dp[i] = dp[i - 1] + dp[i-2];//递推公式
        }
        return dp[n];//求第n个斐波那契数
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n) 

递归法:

class Solution {
public:
    int fib(int n) {
        if(n < 2)return n;
        return fib(n - 1) + fib(n - 2);
    }
};

• 时间复杂度：O(2^n)
• 空间复杂度：O(n)，算上了编程语言中实现递归的系统栈所占空间

3.爬楼梯（70题）

题目描述：

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

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

注意：给定 n 是一个正整数。

示例 1：

• 输入： 2
• 输出： 2
• 解释： 有两种方法可以爬到楼顶。
  • 1 阶 + 1 阶
  • 2 阶

动规五部曲：

定义一个一维数组来记录不同楼层的状态

1. 确定dp数组以及下标的含义

dp[i]： 爬到第i层楼梯，有dp[i]种方法

dp[i] = dp[i - 1] + dp[i - 2] 

不考虑dp[0]如何初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。

确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 1)return n; 因为下面直接对dp[2]操作了，防止空指针
        vector<int>dp(n+1);
        dp[1] = 1;
        dp[2] = 2;
        // 注意i是从3开始的
        for(int i = 3;i <= n;i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

4.使用最小花费爬楼梯 （746题）

题目描述：

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1：

• 输入：cost = [10, 15, 20]
• 输出：15
• 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

  动态规划：dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。

可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？

一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

初始化 dp[0] = 0，dp[1] = 0，，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int>dp(cost.size()+1);//定义数组
        dp[0] = 0;//初始化
        dp[1] = 0;
        //从i = 2从前向后遍历
        for(int i = 2;i <= cost.size();i++){
            dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);//递推公式
        }
        return dp[cost.size()];
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

5.不同路径 （62题）

题目描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

深搜：

class Solution {
private:
    int dfs(int i, int j, int m, int n) {
        if (i > m || j > n) return 0; // 越界了
        if (i == m && j == n) return 1; // 找到一种方法，相当于找到了叶子节点
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }
public:
    int uniquePaths(int m, int n) {
        return dfs(1, 1, m, n);
    }
};

动态规划：dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。

此时在回顾一下 dp[i - 1][j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。

那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。

首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理

递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。

这样就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>>dp(m,vector<int>(n,0));//定义dp二维数组，大小为mxn
        for(int i = 0;i < m;i++)dp[i][0] = 1;//首先对最上面一行进行初始化为1
        for(int j = 0;j < n;j++)dp[0][j] = 1;//对最右边的一列初始化为1
        //我们沿着从左到右，从上到下遍历的顺序进行遍历
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];//递推公式
            }
        }
        return dp[m-1][n-1];//返回值
    }
};

• 时间复杂度：O(m × n)
• 空间复杂度：O(m × n)

 数论方法：

在这m + n - 2 步中，一定有 m - 1 步是要向下走的，不用管什么时候向下走。

那么有几种走法呢？ 可以转化为，给你m + n - 2个不同的数，随便取m - 1个数，有几种取法。

那么这就是一个组合问题了。

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long numerator = 1; // 分子
        int denominator = m - 1; // 分母
        int count = m - 1;
        int t = m + n - 2;
        while (count--) {
            numerator *= (t--);
            while (denominator != 0 && numerator % denominator == 0) {
                numerator /= denominator;
                denominator--;
            }
        }
        return numerator;
    }
};

• 时间复杂度：O(m)
• 空间复杂度：O(1)

总结：

 动态规划理论基础：动态规划是一个问题有很多子问题时候使用非常适合，其是由上一个状态推到出来的，贪心算法是由局部最优推出全局最优，动态规划五部曲，定义dp数组，初始化，遍历顺序，递推公式，打印

斐波那契数: F(n) = F(n - 1) + F(n - 2)数列需要满足这个条件，我们首先定义dp数组，第i个数的斐波那契数值是dp[i]，初始化，根据状态转移公式，我们需要知道两个初始值，dp[0] = 0，dp[1] = 1，根据状态转移公式知道遍历顺序是从前向后遍历，递推公式就是题目条件，注意细节i遍历起始和终止位置

爬楼梯：总共有N个台阶，每一次可以走1或2个台阶，问总共有几种走法能到n台阶，和斐波那契数一个道理，首先设置dp数组，dp代表爬到i层楼梯有dp[i]种方法，初始化，dp[1] = 1，dp[2] = 2，从i=3开始遍历，从前向后遍历，dp[i] = dp[i - 1] + dp[i - 2]递推公式，注意递归的边界问题

使用最小花费爬楼梯：dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]，可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])，初始化 dp[0] = 0，dp[1] = 0，从前到后遍历，注意i 的遍历范围i=2开始还要注意终止条件。

不同路径：dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径定义dp数组，dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，首先对最上面一行进行初始化为1，对最右边的一列初始化为1，我们沿着从左到右，从上到下遍历的顺序进行遍历。