那么本篇文章就正式进入了动态规划的算法的学习，那么动态规划算法也可谓是算法内容中的一座大山，那么在大厂算法笔试乃至算法比赛中出现的频率也逐渐变高，那么可见学习好动态规划算法的一个重要性，那么对于动态规划最难理解的，不是动态规划的题，而是动态规划的一个算法思想，我认为其实学习掌握一个算法，并不是说你会做这个算法所对应的题就好了，题一直在变，而算法的思想是不变的，所以掌握理解清楚算法的思想是最为关键，那么废话不多说，我们就来进入动态规划的学习！
动态规划原理
你也许会听到过动态规划的相关的专有名词，比如最优子结构，无后效性，但是了解这些其实对我们学习掌握动态规划的算法没有什么用，而这些名词只有当我们真正学懂之后，回过头来看才知道他们表达的含义
那么其实动态规划也是一样有套路的，首先动态规划的本质其实就是一个枚举，只不过是一个高效的枚举
那么假设现在我们有一个有限数量的一个集合，那么在这个集合中的元素都是一个一个的方案，那么我们要在这个集合中选择出最优秀的一个方案，那么我们如何得到这个最优秀的方案呢，那么我们的首先想到的常规思路就是我们直接去枚举出存在在这个集合中所有的方案，那么只要我们枚举得到在这个集合中的所有方案，那么我手上已知了该集合中的所有方案，那么我最终就可以筛选出最优秀的方案
首先这个思路肯定是没问题的，主打的就是一个暴力枚举，但是假设我们这个有限集的元素的数量很多，并且如果是指数级别的，那么枚举存在在这个元素当中所有的方案的时间代价就很大，意味着我们得换一种思路来进行一个枚举，我们知道我们的最优秀的方案就是集合中的其中一个元素，我们现在的目标就是找到这个元素，那么我们可以将我们的集合给划分成k个部分，那么这k个集合中每一个集合有着各自的一个最优方案，那么我们整个集合的最优方案就在这k个集合所对应的最优方案中筛选出最优秀的则是我们整个集合当中的最优方案。
那么我们现在就从枚举着整个集合变成了枚举这个集合当中的k个子集，那么我们此时枚举的样本量就减小了，那么同理我们对于这k个集合中，我们可以采取同样的方式，将我们这k个集合划分成一个更小的子集，然后去枚举这更小的子集，那么同理我们的更小的子集还可以再进行划分直到划分成最小的子集，那么我们就从这个最小的子集往上推，因为我们要求解当前集合的最优解，那么就需要当前各个子集的最优解，然后从中筛选出最优秀的作为当前整个集合的最优解，意味着我们这个集合的解的确定就需要该集合中子集的解的确定，那么一旦该子集的解确定了，那么整个集合的解就确定了。
那么我们这种方式，相比于我们直接暴露枚举出在这个集合当中的每一个元素，然后筛选出最优解，我们动态规划的方式则是不枚举整个集合，而是将这个集合给拆分成更小的子集，那么去枚举这个子集，那么一旦子集的解确定了，那么我们整个集合的解就确定了，那么我们枚举的样本量就大大减小，提高了效率。
那么现在你知道了动态规划的一个原理，你肯能就有一个问题：
1.我怎么划分这个集合？2.划分好集合之后又怎么求这个集合的解呢？
那么第一个问题我们就根据我们该解的最后一步来进行划分，那么你现在你可能不知道该解的最后一步是什么意思，不用担心，我在之后的题目会讲解，你先记着这句话。
而对于第二个问题，首先我们要的确定我们集合的解的含义，那么我们的集合的解我们在动态规划中称之为状态，而当前集合的状态是未知的，那么该集合的状态的确定需要其该集合的子集的状态的确定才可以确定该集合的状态，所以我们要确定该集合的状态，也就是要求解该集合的解，那么我们就一定要确定该集合的依赖关系，它依赖哪些子集的状态，而这个依赖关系我们会用一个状态转移方程来表示，那么该方程就是我们首先确定了该集合要依赖哪些子集的状态，并且有了子集的状态之后又怎么计算得到最终该集合的状态，就是我们状态转移方程的内容，所以我们动态规划的问题的核心就是定义状态以及确定状态转移方程，但是我们这些状态得有一个起始条件，因为我们这个集合不可能一直不断划分下去，那么肯定有一个划分的最小子集，那么该子集的解我们是可以直接确定的，也就是起始条件，那么从该子集的解利用状态转移方程来递推得到之后的集合的解，所以一旦确定完起始条件和状态转移方程后，我们这个动态规划题基本上已经离AC不远了。
而刚才我们将一个有限集给不断划分成子集的过程，我们可以通过递归来实现，因为我们递归就是可以将一个问题划分成一个更小规模的子问题，其中这个划分成更小规模的子问题，就是我们递归中的“递”过程，那么一旦划分到最小子问题之后，那么我们就能够往上回溯返回该子问题的解，一旦有了该该问题所需要的所有的子问题的解，那么该问题的解自然也就能求出了，所以我们可以用递归来尝试得到我们的动态规划，这也就是我们DFS加上记忆化搜索得到我们的动态规划，如果是新手的话，那么可以通过这个方式来来修改得到动态规划的策略，但是这个方法只适合新手，我不推荐，因为只要你看懂我上文的原理，我们动态规划直接零帧起手，分析题意，确定状态，写出状态转移方程，相比于麻烦的递归它不香吗。
那么接下来我就会用几个题来讲讲我是如何应用这个动态规划的算法思想来解决的
动态规划的应用
题目一：最小硬币数量
题目：现在我们有面值为2元，5元，7元的3种硬币，那么我们要取超市买一个价格为k元的商品，要求只能用这三种类型的硬币来付款，那么请问我们用硬币凑出刚好付清这个商品的价格k的前提下，用的硬币的最少数量是多少？
题目分析：那么这里我们知道我们要求刚好付清价格且硬币最少的数量，那么这里我们的常规思路可以就是枚举出所有的满足前提条件也就是刚好付清价格的方案，然后从这些方案中选择最优方案也就是使用的硬币最少，那么这里我们可以按照这三种类型的硬币可能出现的数量的可能性来进行枚举，其中2元在方案中可能出现的数量是0到k/2个，而我们的5元在方案处可能出现的数量是0到k/5个，同理7元在方案中出现的数量则0~k/7个，那么我们将这三种类型的硬币每一个硬币可能出现的数量情况给组合那么就可以得到我们其中的一个方案，那么枚举的过程就是一棵多叉树，而此时该硬币数量可能出现的数量情况的决策就是该多叉树的一个节点，而它可能出现的数量就是该节点对应的一个一个分支，那么这里从顶部到达底部的一个个路径就是其中可能满足前提条件的方案，那么我们从这棵多叉树的顶部遍历到底部然后往上回溯的过程中，那么每个节点都会返回该节点对应的硬币数量，那么回溯到顶部，我们就可以综合得到每一个路径上也就是每一个方案的硬币数量，然后得到最优解
那么上面是我们的暴力方法，我们直接暴力枚举所有的满足前提的方案从中得到最优，但是我们一旦金额k的数值过大，那么这个枚举要对应遍历的多叉树的节点以及路径就会增大很多，那么时间开销就随之增大，那么暴力枚举肯定是不可取的做法
那么这里我们就要得到我们动态规划的一个策略，那么我们这里我们要从满足前提条件的方案中筛选出最优秀的方案，也就是硬币数量最少且刚好付完款的方案，那么我们知道这个方案一定是有很多步决策所组成，在此题中也就是我们付的哪些硬币，那么付的这一个一个硬币就是其中的一个个决策，那么意味着我们要求得到最优方案，我们只要知道这一步步决策是什么就可以得到
那么既然存在这个最优的方案，那么我们知道这个方案有很多步决策所组成，那么它一定有最后一步，而我们知道我们的最优方案它的最后一步一定是我们付的这三个硬币的其中一种，那么我们就可以根据最后一步来进行划分，那么我们要求我们这个满足前提的最优方案，那么我们可以求得满足前提的情况下且付的最后一个硬币是2元的最优方案和满足前提的情况下且付的最后一个硬币是5元的最优方案和满足前提的情况下且付的最后一个硬币是7元的最优方案，那么我们整体的最优方案一定是从这三个方案中抉择出，那么我就将这个集合按照最后一枚硬币给要枚举的集合划分成了三份，那么同理我们对于其中满足前提的条件下且付的最后一个硬币是2元的最优方案，那么它的也一定是由之前满足前提条件下也就是付完k-2元且最后付的一枚硬币是2或者5或者7元的最优方案所筛选得到，那么相当于我们有将这个子集可以按照之前的方式在划分成三等分再来进行枚举
那么这里我们就可以确定状态，那么定义我们的状态是付完i元的前提下需要的最少的硬币数量，那么我们定义好状态我们在来确定我们的起始状态，那当我们付的物品的价钱是0元的时候，那么我们付的硬币数量就是0，那么这就是我们的起始条件，那么确定好初始状态，我们根据我们之前的分析，我们付的k元的最优方案依赖于付完k元且最后一枚硬币是2元和5元以及7元的各自最优方案的确定，那么这里我们确定了它依赖的子集，那么计算方式就是我们对于这三个子集的解求一个最大值即可，所以我们可以定义一个dp数组，记录每个子集的答案然后往后递推：
起始条件：dp[0]=0
状态转移方程：dp[i]=min(dp[i-2]+1,dp[i-2]+1,dp[i-7]+1)
class solution
{
public:
int mincoinNum(int price)
{
vector<int> dp(price+1,INT_MAX);
dp[0]=0;
for(int i=1;i<dp.size();i++)
{
if(i-2>=0)
{
dp[i]=min(dp[i],dp[i-2]+1);
}
if(i-5>=0)
{
dp[i]=min(dp[i],dp[i-5]+1);
}
if(i-7>=0)
{
dp[i]=min(dp[i],dp[i-7]+1);
}
}
if(dp[price]!=INT_MAX)
{
return dp[price];
}
return 0;//假设不存在满足前提的最优解
}
}
那么这里我们再来看一下我们动态规划的思想在此题的应用，那么我们首先知道要求最优方案，那么我们该方案一定是由很多步很多决策所组成，在此题这个决策就是付的每一枚硬币就是我们的一步步决策，那么最优解既然存在，那么它一定有最后一步，也就是付的最后一枚硬币，那么这最后一枚硬币要么是2元要么是5元要么是7元，那么我们就可以通过最后一步要我们枚举的集合按照最后一步划分成了三个子集，然后求这三个子集的解，那么这三个子集又可以按照同样的性质来划分，所以接下来我们就只需要确定状态以及根据依赖关系确定状态转移方程即可
所以我们动态规划的一个基本的做题套路就是：
首先分析题意，确定状态，
根据状态确定起始条件与状态转移方程
根据状态转移方程来递推
注意：我们定义状态的时候，我们的状态定义一定要包含区间信息，因为我们知道我们子集的解一定是当前集合中的解，而不是其他集合或者含有不包含该集合的内容的解，所以这题我们定义状态的时候专门加了区间来修饰约束，也就是付完前i元，那么不加这个内容，便无法进行状态转移
题目二：出去游玩的最小花费
题目：现在有一个数组nums，数组里面的元素代表我们第几天出去游玩，那么数组的元素的值nums[i]的取值范围大于0小于365，那么我们出去的游玩的天数都要买票，那么现在有三种类型的票，分别是只能仅限于当天游玩使用，和能覆盖连续一周的票，和能够覆盖连续一个月的票，这三种类型的票价格分别是a,b,c元那么我们要求每一天都有票的情况下所花费最少的价格是多少
例子：[1,2,3,10,20]
我们可以这5天都分别买第一种类型的票，花费5a元或者先买第二种类型的票覆盖1,2,3天，然后第10天和第20天买第一种类型的票，总共花费b+2a元，或者直接买第三种类型的票覆盖该月所有天数花费c元
题目思路：那么这里我们知道我们这个问题还是求一个最优方案问题，我们要在满足前提的条件下也就是覆盖完所有的游玩天数的方案中筛选出最优方案，那么这里的最优方案的组成是由一步一步决策所组成，也就是不同天数下买的什么类型的票所构成，同样既然存在最优解，那么最优解一定存在最后一个决策，也就是我们最后选择的哪种类型的票，那么最优解的最后一个决策无非要么就是买了第一种类型的票，要么就买了第二种或者第三种类型的票，所以我们可以按照最后一步的策略，将我们要枚举的满足前提条件的集合按照最后一步给划分成三份，也就是满足前提条件下且最后买的票是第一种类型的最优解和满足前提条件下最后买的票是第二种类型的最优解和满足前提的条件下买的票是第三种类型的最优解，那么我们的整体的最优解就依赖于这三个子集，那么同样我们的这三个子集也可以按照同样的方式来划分，那么我们就可以定义状态为：在覆盖完当前第i天时，我们的最小花费
我们知道我们依赖的子集是最后一步买的三种不同类型的票的最优解，那么我们有了这三个子集的最优解，我们的计算方式就是取一个最小值，而初始条件就是我们当游玩的第0天的时候，所花费就是0，那么这就是我们的初始条件，最后定义一个dp数组来存储我们一个子集的解
代码实现：
class Solution {
public:
int mincost(vector<int>& days, int a, int b, int c) {
int n = days.size();
if (n == 0) return 0; // 处理空输入
sort(days.begin(), days.end()); // 确保天数已排序
vector<int> dp(n + 1, INT_MAX); // 正确初始化dp数组大小为n+1
dp[0] = 0; // 第0天（无游玩天）花费为0
for (int i = 1; i <= n; ++i) {
// 1. 单日票方案
dp[i] = dp[i - 1] + a;
// 2. 周票方案
// 找到第一个j，使得 days[i-1] - days[j] < 7
int j = i - 1;
while (j >= 0 && days[i-1] - days[j] < 7) j--;
dp[i] = min(dp[i], dp[j + 1] + b); // j+1是覆盖区间的起点
// 3. 月票方案
// 找到第一个j，使得 days[i-1] - days[j] < 30
j = i - 1;
while (j >= 0 && days[i-1] - days[j] < 30) j--;
dp[i] = min(dp[i], dp[j + 1] + c);
}
return dp[n];
}
};
题目三：机器人走棋盘
题目：有一个机器人位于一个 m x n 的棋盘的左上角（起始位置为 (0, 0)）。棋盘上的每个位置都有一个非负整数，表示该位置的代价。机器人每次只能向下或向右移动一格。目标是找到一条从左上角到右下角（位置 (m-1, n-1)）的路径，使得路径上的总代价最小。
题目思路：那么这里我们知道我们要求能从左上角走到右下角的代价最小的路径，那么这里我们还是要从满足前提的条件下也就是能从左上角走到右下角的所有路径中选择其中最优秀的情况也就是代价最小的，那么我们这个最优解同样也是由一步步决策所组成的，那么这里的决策就是在该棋盘上的位置选择走的方向是向右还是向下，那么我们还是来看这里的最后一步，那么我们知道我们每一个最优解的方案它要么是从右下角的上面一个格子往下走到达该右下角或者从右下角的左边的一个格子往右走到达右下角，所以我们的最优解一定是我们从左上角中出发最后一步到达右下角的上方的最小代价和从左上角出发最后一步到达右下角的左侧的最小代价中抉择出最优秀的解作为答案，而我们到达我们的右下角的上方同理也是从该位置的上方以及左侧到达，那么我们要确定从左上角到达右上角的上方的最小代价就得依赖他的上方以及它的左侧的最小代价，那么这里我们就可以定义状态：从左上方到当前的(i,m)位置处的最小代价
那么我们该位置的状态的确定则依赖于它的上方以及左侧的状态，具体计算方式则是得到最小值，那么我们有了依赖关系以及如何计算得到该位置的状态后，我们就可以写出状态转移方程，那么我们的起始条件就是我们的第一行以及第一列的最小代价，因为题目规定机器人只能往下或者往右左，所以我们到达第一行以及第一列的位置只能从左上角往右或者往下走，所以我们能确定他们的状态
接着我们建立一个二维的dp数组，那么数组的每个位置对应棋盘的每个位置代表当前左上角到当前位置的最小代价，那么我们将每个位置的最小代价记录到该数组中，由于我们有了第一行以及第一列，那么我们就从第二行的第二列开始从左往右依次计算即可
dp[m-1] [n-1]则是最后的答案
class solution
{
public:
int mincost(vector<vector<int>> nums)
{
vector<vector<int>> dp(nums.size(),vector<int>(nums[0].size()));
dp[0][0]=nums[0][0];
for(int i=1;i<nums.size();i++)
{
dp[0][i]=dp[0][i-1]+nums[0][i];
}
for(int i=1;i<nums[0].size();i++)
{
dp[i][0]=dp[i-1][0]+nums[i][0];
}
for(int i=1;i<dp.size();i++)
{
for(int j=1;j<dp[0].size();j++)
{
dp[i][j]=min(dp[i-1][j]+nums[i][j],dp[i][j-1]+nums[i][j]);
}
}
return dp[dp.size()-1][dp[0].size()-1];
}
}
题目四：01背包
题目：现在我们有一个体积为m的背包和N件物品，那么每件物品只能使用一次，第i件物品的体积为v[i]，价值为k[i]，求解将哪些物品装入背包，在不超过背包容量的前提下，能够装的总价值最大，输出这个总价值。
题目思路：那么这里我们知道我们要求满足前提的条件下的最优解，而对于该题来说，那么满足的前提就是不超过背包总的容量v，那么我们要从满足该前提的方案中筛选出最优秀的方案，而这里我们的方案由一步一步的决策所构成，也就是每一个位置的物品选择与不选择的决策组合就是我们的方案，那么同理对于我们的最优解来说，那么它也是由这每一步的决策所组成，那么同理，它的最后一步决策就是最后一个位置的物品选或者不选，那么它就依赖于我们满足前提也就是不超过背包总容量v的最后一个物品不选择的最优方案和不超过背包总容量v选择最后一个物品的最优方案，我妈根据最后一个位置选或者不选将我们要枚举的集合划分成两个子集，那么我们可以在从这两个子集中筛选，再按照相同的方式进行一个划分。
那么这里我们就来定义我们的状态，那么之前就说过我们定义我们的状态一定要和集合有关，也就是区间有关，还要跟我们题目要求的答案所满足的性质有关，那在本题的区间就是物品的一个位置，而答案的要满足的性质是不超过容量，那么在之前的状态中，我们集合的解只与集合的区间有关，那么我们的解就好比一次函数对应的因变量，而这里的区间在此题中只是其中的一个自变量，那么我们只有该一个自变量求不出解来，那么就需要另一个自变量也就答案所具有的性质：不超过背包容量v，所以此题我们定义状态：在选择k个物品其容量不超过j的前提下，所能够获得的最大价值
然后根据我们前面的集合划分，我们知道依赖关系就是最后一步选或者不选的子集，那么有了依赖的子集的状态之后，计算方式则是取最大值，那么这样我们的状态转移方程就可以写出来了，那么这里我们定义一个二维的dp数组由于这题的状态是由两个自变量约束，那么我们就得用一个二维数组来记录不同的子集的解
class Solution {
public:
int maxValue(std::vector<int> volumes, std::vector<int> values, int maxVolume) {
int n = volumes.size();
// 创建 dp 数组，dp[i][j] 表示考虑前 i 个物品且体积不超过 j 时的最大价值
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(maxVolume + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= maxVolume; ++j) {
if (j - volumes[i - 1] >= 0) {
// 选择当前物品或者不选择当前物品
dp[i][j] = std::max(dp[i - 1][j - volumes[i - 1]] + values[i - 1], dp[i - 1][j]);
} else {
// 当前物品无法装入背包
dp[i][j] = dp[i - 1][j];
}
}
}
// 返回考虑所有物品且体积不超过 maxVolume 时的最大价值
return dp[n][maxVolume];
}
};
结语
那么我们动态规划解决的题的特征一般就是求最优解或者最值以及计数问题
那么我们可以采取集合的方式来理解我们的动态规划，动态规划的本质其实就是一个枚举，原本我们要从一个指数个级别的元素的集合中去筛选出一个满足条件的解，那么我们首先可以将我们这个集合给划分成k份，从这k份中得到相应的满足条件的解，然后这k份子集的解的确定又要根据其对应依赖的子集的解来确定，所以最后需要定义起始状态与状态转移方程来进行递推。
那么这就是本篇文章的全部内容，我后续还会更新动态规划的内容，那么这篇文章更多的是理解认识动态规划的思想，认识到动态规划的一个思维方式，感谢你能耐心看完本文，如果本文对你有帮组的话，希望你多多三连支持哦！
