目录
前言
Part1. 爬楼梯
Part2. 打家劫舍
Part3. 完全平方数
Part4. 零钱兑换
Part5. 结语
前言
动态规划作为经典的算法之一，他广泛分布在面试题，竞赛题当中，是我们非常有必要了解的算法。接下来，跟随小编的步伐来窥见这个算法的精妙吧。
let's go!!!!!!!!!
Part1. 爬楼梯
正所谓：“九层之台，起于累土。千里之行，始于足下。” 要理解动态规划这个蕴含着丰富内涵的算法，我们要先从最基础的模型开始理解。接下来，让我们来看看吧：
Leetcode链接：70. 爬楼梯 – 力扣（LeetCode）
这道题的关键就在于：我们要反向去思考。也就是：
那么我们要怎么解决这个问题呢？关键在于保留数值，我们要计算n处的方法数，就要知道n-1和n-2他们两个的方法数，n处的方法数也只与这两个有关。
同时，我们已经知道的信息是前面的方法数，n=1处他的方法数就为1，n=2处方法数就为2,我们就可以推导出三，二和三就可以推导出四，循环往复。即我们有：
int climbStairs(int n) {
//特殊情况讨论
if(n==1)
return 1;
if(n==2)
return 2;
//初始化变量
int left=1;//从前往后算
int right=2;
int move=0;
n-=2;
//主循环
while(n–)
{
move=left+right;//不断滚动向前 进行n次
left=right;
right=move;
}
//return
return move;
}
这样我们就解决了这个问题，总结以上我们的推导过程我们就可以总结出：
“对于动态规划类的题目，我们要反向思考（后面的状态是由前面决定的），正向实现（前面保留状态推导后面的，后面的结合前面的，再推导更后面的，循环往复。）”
接下来我们还会不断深化这个结论。
Part2. 打家劫舍
先来看题目：
Leetcode链接：198. 打家劫舍 – 力扣（LeetCode）
首先，第一点（反向思考）：
其次，我们要怎么算出来S4和S5呢（正向实现）：
我们来看看代码实现吧：
int max(int a,int b)
{
return a>b?a:b;//返回最大值
}
int rob(int* nums, int numsSize) {
if(numsSize==1)//特殊情况讨论
{
return nums[0];
}
int left=0;
int right=0;
int* dp=(int*)malloc(numsSize*sizeof(int));//dp数组存最值 dp[x]~Sx
for(int i=0;i<numsSize;i++)
{
dp[i]=max((i-2<0)?0:dp[i-2],(i-3<0)?0:dp[i-3])+nums[i];//按照上面所讲的公式 同时要注意数组越界的情况
}
return max(dp[numsSize-1],dp[numsSize-2]);
}
这样我们就完成了这道题，看起来还是比较简单的对吧，只要遵守上面的总结：反向思考，正向实现。就可以解决啦，我们来看下一个：
Part3. 完全平方数
先来看题目：
Leetcode题目链接：279. 完全平方数 – 力扣（LeetCode）
首先，反向思考：
通过上面的过程，我们已经知道了求值的手段，接下来我们来看看正向实现吧。
正向实现：
基本的逻辑理顺了，我们来看代码实现：
int numSquares(int n) {
//初始化变量
int* min_sum=0;
int m=0;//循环参数 主循环 为min_sum赋值
int q=0;//循环参数 副循环 遍历得出min_sum的值
int min_may=INT_MAX;//可能的最小的平方数
int tem1=0;//临时变量1
int tem2=0;//临时变量2
//开辟数组min_sum
min_sum=(int*)malloc((n+1)*sizeof(int));//存储前面的最小完全平方数组成数
min_sum[0]=0;//0固定为0 方便本身是完全平方数的计算
//遍历数组
for(m=1;m<=n;m++)//从前往后走 一步一步算出每一步的最小完全平方数组成数
{
for(q=1;;q++)//遍历每个完全平方数
{
tem1=m-q*q;
if(tem1<0)
break;
else
{
tem2=min_sum[tem1]+1;
if(tem2<=min_may)
{
min_may=tem2;//维护最小完全平方数组成数
}
}
}
min_sum[m]=min_may;
min_may=INT_MAX;//记得每一次要还原哦
}
//return
return min_sum[n];//返回n处的最小完全平方数组成数
}
这道题依旧贯彻我们上面的思想，我们来看最后一题：
Part4. 零钱兑换
先来看题目：
Leetcode题目链接：322. 零钱兑换 – 力扣（LeetCode）
其实我们一看就会发现，这道题和完全平方数非常相似。都是要用一些特殊的数字凑出一个数字，上面是完全平方数，这里就是给出的数字。由于完全平方数有1的存在，所以每个数都可以凑出来，而这里不是这样的。不过也还是非常相似，我们来看代码：
int coinChange(int* coins, int coinsSize, int amount) {
//初始化变量
int* min_num = (int*)malloc((amount + 1) * sizeof(int));//存储每个位置由给出的数字最少组成数目
min_num[0] = 0;
int move = 1;
int* result = (int*)malloc(coinsSize * sizeof(int));//存储当前数字减去每个给出数字的结果 方便后续使用
int min = INT_MAX;
//循环
while (move <= amount)//由左向右遍历 直到到达目标数字
{
for (int i = 0; i < coinsSize; i++)
{
result[i] = move – coins[i];//得到当前数字减去给定数字的全部结果
}
for (int i = 0; i < coinsSize; i++)
{
if (result[i] < 0)//小于0不用管
{
continue;
}
if (min_num[result[i]] < min&&min_num[result[i]]!=-1)
{
min = min_num[result[i]] + 1;//当这个不为-1时 更新最小值
}
}
if (min != INT_MAX)
{
min_num[move] = min;//记录最小值
}
else
{
min_num[move] = -1;//当这个最小值没改变时 说明这个位置不能被给出的数字组成
}
min = INT_MAX;//还原
move++;//往后走
}
return min_num[amount];
}
同样是贯彻了我们上述的思想，结合上面完全平方数的流程，还是非常easy的。
Part5. 结语
通过上面对4道题目的介绍，我们初步了解了动态规划算法。我认为：反向思考，正向实现，是这些题目比较普适的思想。
希望这篇博客可以给大家带来帮助。
最后，祝大家可以：春风得意马蹄疾，一日看尽长安花！
最后的最后，要是觉得本文还可以的话，可以点点赞，关注小编一波，谢谢大家！~
