[数据结构与算法]【算法刷题】——动态规划基础篇

📄个人主页：胖虎不秃头
?个人简介：Java领域新星创作者，随时准备跑路的大二学生
🔥精品专栏：有这一个就够了
🌈个人名言：知道的越多，不知道的越多
💥刷题神器：推荐一款算法刷题网站Nowcoder👉点击跳转刷题网站进行注册学习

动规的五部曲：

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

1、斐波那契数

描述

斐波那契数，通常用 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数组
   当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);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[N];
    }
};

不需要记录整个数组，只需要维护两个数值就可以

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

2、爬梯子

描述

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

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例

示例 1：

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

示例 2：

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

思路分析

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

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

2. 确定递推公式

   首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶就是dp[i]。

   还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶就是dp[i]。

   所以dp[i] = dp[i - 1] + dp[i - 2] 。

3. dp数组如何初始化

   dp[1] = 1，dp[2] = 2

4. 确定遍历顺序

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

5. 举例推导dp数组

题解

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;
        for (int i = 3; i <= n; i++) { // 注意i是从3开始的
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

这道题目还可以继续深化，就是一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶。

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) { // 把m换成2，就可以AC爬楼梯这道题
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};

3、最小花费爬楼梯

描述

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

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

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

示例

示例 1：

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

示例 2：

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解释：最低花费方式是从
cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

思路分析

注意：假设数组 cost 的长度为 n，则 n 个阶梯分别对应下标 0 到 n?1，楼层顶部对应下标
n，问题等价于计算达到下标 n 的最小花费。可以通过动态规划求解。
算法

• 确定dp数组以及下标的含义
  • 定义 dp[i] 表示从楼梯的第 i 阶楼梯向上爬需要支付的最少费用；
• 确定状态转移方程
  • 当 2≤i≤n 时，可以从下标 i?1 使用 cost[i?1] 的花费达到下标 i，或者从下标 i?2 使用cost[i?2] 的花费达到下标 i。为了使总花费最小，dp[i] 应取上述两项的最小值，因此状态转移方程如下：dp[i]=min(dp[i?1]+cost[i?1],dp[i?2]+cost[i?2])
• 初始化状态
  • 由于可以选择下标 0 或 1作为初始阶梯，因此有dp[0]=dp[1]=0。
• 遍历顺序
  • 由状态转移方程知道 dp[i]是从 dp[i?1]和dp[i?2] 转移过来所以从前往后遍历。
• 返回值
  • 因为一共计算 n 阶楼梯最小花费，所以返回 dp[n]。

题解

class Solution {
public:
    /* 动态规划五部曲：
    1.确定dp[i]的下标以及dp值的含义： 从楼梯第i个台阶向上爬需要支付的费用dp[i]；
    2.确定动态规划的递推公式：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    3.dp数组的初始化：你可以选择从下标为 0 或下标为 1 的台阶 开始爬楼梯 dp[0] = 0, dp[1] = 0;
    4.确定遍历顺序：分析递推公式可知当前值依赖前两个值来确定，所以递推顺序应该是从前往后；
    5.打印dp数组看自己写的对不对；
    */
    int minCostClimbingStairs(vector<int>& cost) {
        /* 定义dp数组 */
        vector<int> dp(cost.size()+1);
        /* dp数组初始化 */
        dp[0] = 0;
        dp[1] = 0;
        /* 从前往后遍历 */
        for (int i = 2; i <= cost.size(); i++) {
            /* 
            dp[i]代表从楼梯第i个台阶向上爬需要支付的费用，所以需要到达dp[i]有两种方法：
            1:从dp[i-1]花费cost[i-1]的费用可以到达dp[i];
            2:从dp[i-2]花费cost[i-2]的费用可以到达dp[i];
            需要最少的费用就是两者去最小值；
            */
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.size()];
    }
};

疑点分析

请问dp[0]和dp[1]的初始化值是怎么确定都为0的呢？

对题意两种理解，一种是把cost[i]理解为从前一步到达第i个台阶的成本，另一种是把cost[i]理解为从第i个台阶往上走一步的成本。题解采用的是第二种，就忽略了最开始两个台阶的成本，因此为dp[0]和dp[1]初始化为0

刷题神器

算法的学习必须是有条理、有逻辑的由浅入深，一定要理论+实践结合，不管你是刚入门的小白，还是曾经学过相关知识，或者有一定基础，想要继续提升能力，又或者面试前突击想刷刷真题，都可以去牛客网练习！

牛客网做为国内内容超级丰富的IT题库，尤其是他的算法内容，从入门到大厂真题，完全覆盖了所有算法学习者的必备内容

从小白入门到某度、某音、某东的真实场景全部覆盖，只要想学习算法，那一定不能错过牛客网！而且内容全部免费，赶紧刷起来！👉点击跳转刷题网站进行注册学习