【动态规划】——理论基础,经典例题1

绝地灬酷狼 2023-09-27 17:17 132阅读 0赞

##  ##

> ## 前言 ##
> 
> 小亭子正在努力的学习编程，接下来将开启算法的学习~~
> 
> 分享的文章都是学习的笔记和感悟，如有不妥之处希望大佬们批评指正~~
> 
> 同时如果本文对你有帮助的话，烦请点赞关注支持一波, 感激不尽~~

**目录**

前言

什么是动态规划？

解决动态规划问题的基本思路

动归五部曲：

经典例题第一组

第一题：斐波那契数

用动归五部曲分析此题：

下面用java代码实现：

第二题：爬楼梯

动规五部曲解题：

java代码实现：

第三题： 使用最小花费爬楼梯

动归五部曲：

用java代码实现：

--------------------

## **什么是动态规划？** ##

**动态规划是分治思想的延伸，通俗来说就是 大事化小小事化了的艺术，能使用动态规划来解决的问题一般具备以下几个特点：**

*  **1.把原来的问题分解成几个相似的问题**
 *  **2.所有子问题都只需要解决一次**
 *  **3.存储子问题**

**所以动态规划中每⼀个状态⼀定是由上⼀个状态推导出来的**

【这⼀点就区分于贪⼼，贪⼼没有状态推导，⽽是从局部直接选最优的。】

## 解决动态规划问题的基本思路 ##

> ### **动归五部曲：** ###
> 
> 1.  确定dp数组（dp table）以及下标的含义
> 2.  确定递推公式【这个递推公式就是状态转化方程】
> 3.  dp数组如何初始化
> 4.  确定遍历顺序
> 5.  举例推导dp数组

了解了动态规划的基本理论，和动归五部曲，下面就让我们到题目中去感受一下动归五部曲怎么具体解决问题的吧~~~

## 经典例题第一组 ##

### 第一题：斐波那契数 ###

[刷题链接：509. 斐波那契数 - 力扣（LeetCode）][509. _ - _LeetCode]

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

#### **用动归五部曲分析此题：** ####

> **动规五部曲：**  
> 这⾥我们要⽤⼀个⼀维dp数组来保存递归的结果  
> **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为10的时候，dp数组应  
> 该是如下的数列：  
> 0 1 1 2 3 5 8 13 21 34 55
> 
> **如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是⼀致  
> 的。**  
> 以上我们⽤动规五部曲的⽅法分析完了
> 
> ####  ####
> 
> #### **下面用java代码实现：** ####
> 
>     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];
>     
>         }
>     }

### 第二题：爬楼梯 ###

[力扣题目链接(opens new window)][opens new window]

假设你正在爬楼梯。需要 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\]呢？
> 
> 从dp\[i\]的定义可以看出，dp\[i\] 可以有两个方向推出来。
> 
> 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\]之和！
> 
> 所以dp\[i\] = dp\[i - 1\] + dp\[i - 2\] 。
> 
> 在推导dp\[i\]的时候，一定要时刻想着dp\[i\]的定义，否则容易跑偏。
> 
> 这体现出确定dp数组以及下标的含义的重要性！
> 
> **3、dp数组如何初始化**
> 
> 在回顾一下dp\[i\]的定义：爬到第i层楼梯，有dp\[i\]中方法。
> 
> **需要注意的是**：题目中说了n是一个正整数，题目根本就没说n有为0的情况。
> 
> 所以本题其实不用讨论dp\[0\]的初始化！
> 
> 我相信dp\[1\] = 1，dp\[2\] = 2，这个初始化大家应该都没有争议的。然后从i = 3开始递推，这样才符合dp\[i\]的定义。
> 
> **4、确定遍历顺序**
> 
> 从递推公式dp\[i\] = dp\[i - 1\] + dp\[i - 2\];中可以看出，遍历顺序一定是从前向后遍历的
> 
> **5、举例推导dp数组**
> 
> 举例当n为5的时候，dp table（dp数组）应该是这样的
> 
> ![4194423fe2bf413da5bbdc8aa344459b.png][]
> 
> **此时大家应该发现了，这不就是斐波那契数列么！**
> 
> 唯一的区别是，没有讨论dp\[0\]应该是什么，因为dp\[0\]在本题没有意义！
> 
> ####  ####
> 
> #### java代码实现： ####
> 
>     class Solution {
>         public int climbStairs(int n) {
>              if(n == 1){
>                 return 1;
>             }
>             int[] dp = new int [n+1];
>             dp[1] = 1;
>             dp[2] = 2;
>            
>             for(int i = 3 ; i <= n; i++){
>                 dp[i] = dp[i-1] + dp [i-2];
>             }
>             return dp[n];
>         }
>     }

### 第三题： 使用最小花费爬楼梯 ###

[力扣题目链接][Link 1]

给你一个整数数组 cost ，其中 cost\[i\] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

输入：cost = \[10,15,20\]  
输出：15  
解释：你将从下标为 1 的台阶开始。  
\- 支付 15 ，向上爬两个台阶，到达楼梯顶部。  
总花费为 15 。  
示例 2：

输入：cost = \[1,100,1,1,1,100,1,1,100,1\]  
输出：6  
解释：你将从下标为 0 的台阶开始。  
\- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。  
\- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。  
\- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。  
\- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。  
\- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。  
\- 支付 1 ，向上爬一个台阶，到达楼梯顶部。  
总花费为 6 。

> 分析：
> 
> 题目中说 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于 跳到 下标 0 或者 下标 1 是不花费体力的， 从 下标 0 下标1 开始跳就要花费体力了。
> 
> ### 动归五部曲： ###
> 
> **1、确定dp数组以及下标的含义**
> 
> 使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组dp\[i\]就可以了。
> 
> **dp\[i\]的定义：到达第i台阶所花费的最少体力为dp\[i\]**。
> 
> **2、确定递推公式**
> 
> **可以有两个途径得到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\]);**
> 
> **3、dp数组如何初始化**
> 
> 看一下递归公式，dp\[i\]由dp\[i - 1\]，dp\[i - 2\]推出，既然初始化所有的dp\[i\]是不可能的，那么只初始化dp\[0\]和dp\[1\]就够了，其他的最终都是dp\[0\]dp\[1\]推出。
> 
> 那么 dp\[0\] 应该是多少呢？ 根据dp数组的定义，到达第0台阶所花费的最小体力为dp\[0\]，那么有朋友可能想，那dp\[0\] 应该是 cost\[0\]，例如 cost = \[1, 100, 1, 1, 1, 100, 1, 1, 100, 1\] 的话，dp\[0\] 就是 cost\[0\] 应该是1。
> 
> **但是：**目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 从 到达 第 0 个台阶是不花费的，但从 第0 个台阶 往上跳的话，需要花费 cost\[0\]。
> 
> 所以初始化 dp\[0\] = 0，dp\[1\] = 0;
> 
> **4、确定遍历顺序**
> 
> 最后一步，递归公式有了，初始化有了，如何遍历呢？
> 
> 本题的遍历顺序其实比较简单，简单到很多同学都忽略了思考这一步直接就把代码写出来了。
> 
> 因为是模拟台阶，而且dp\[i\]由dp\[i-1\]dp\[i-2\]推出，所以是从前到后遍历cost数组就可以了
> 
> **5、举例推导dp数组**
> 
> 拿示例2：cost = \[1, 100, 1, 1, 1, 100, 1, 1, 100, 1\] ，来模拟一下dp数组的状态变化，如下：
> 
> ![858ed192a08a4992ae90876d6cb80c4e.png][]
> 
> 如果大家代码写出来有问题，就把dp数组打印出来，看看和如上推导的是不是一样的。
> 
> #### 用java代码实现： ####
> 
>     class Solution {
>         public int minCostClimbingStairs(int[] cost) {
>             int n = cost.length;
>             int[] dp = new int[n+1] ;
>             dp[0] = 0;
>             dp[1] = 0;
>             for(int i =2 ; i < n+1; i++){
>                 dp[i] = Math.min(dp[i-1]+cost[i-1] ,dp[i-2]+cost[i-2]);
>             }
>             return dp[n];
>     
>         }
>     }

以上就是本次分享的内容，后面会继续分享动态规划的解题笔记，关注我，一起刷题~~~~

[509. _ - _LeetCode]: https://leetcode.cn/problems/fibonacci-number/
[opens new window]: https://leetcode.cn/problems/climbing-stairs/
[4194423fe2bf413da5bbdc8aa344459b.png]: https://img-blog.csdnimg.cn/4194423fe2bf413da5bbdc8aa344459b.png
[Link 1]: https://leetcode.cn/problems/min-cost-climbing-stairs/
[858ed192a08a4992ae90876d6cb80c4e.png]: https://img-blog.csdnimg.cn/858ed192a08a4992ae90876d6cb80c4e.png