网站建设ydwzjs,托管公司是怎么托管的,杭州 电子商务网站建设 网络服务,哪些网站用户体验好文章目录 算法原理题目解析第n个泰波那契数列三步问题使用最小花费爬楼梯 从本篇开始总结的是动态规划的一些内容#xff0c;动态规划是算法中非常重要的一个版块#xff0c;因此也是学习算法中的一个重点#xff0c;在学习动态规划前应当要把动态规划的基础知识学习一下
算… 文章目录 算法原理题目解析第n个泰波那契数列三步问题使用最小花费爬楼梯 从本篇开始总结的是动态规划的一些内容动态规划是算法中非常重要的一个版块因此也是学习算法中的一个重点在学习动态规划前应当要把动态规划的基础知识学习一下
算法原理
动态规划既然是一个新的算法这个名字也是新名字那么就要首先明确这个算法的名字代表什么含义
动态规划是什么 动态规划其实就是dp表中的值所表示的含义
那什么又是dp表 dp表是解决这类问题中必须要使用的一个内容通常是借助vector来表示
dp表怎么写出来 一般来说题目要求中会有一些提示同时在分析问题的过程中如果遇到了分析的过程中有重复的子问题也可以借助这个逻辑写出一个状态转移方程利用这个状态转移方程就可以填写到dp表中
状态转移方程 状态转移方程就是在动态规划中根据一部分提示找到dp表的填入方法再根据这个方法就可以借助dp表解决问题因此状态转移方程是解决问题的关键
题目解析
首先用一个比较简单的题目来上手动态规划
第n个泰波那契数列 对于这个题来说可以用上面的动态规划的方法来处理
首先创建一个dp表再从题目中找到状态转移方程再利用状态转移方程写入dp表再利用dp表求出要找的数据
class Solution
{
public:int tribonacci(int n) {// 处理边界if(n0){return 0;}if(n1 || n2){return 1;}// 创建dp表vectorint dp(n1);// 初始化dp表dp[0]0;dp[1]1;dp[2]1;//填入dp表for(int i3;in;i){dp[i]dp[i-1]dp[i-2]dp[i-3];}// 返回值return dp[n];}
};三步问题 分析问题
假设现在有1个台阶那么小孩跳到这个台阶的方法有1种直接从地面走到第一个台阶上
假设现在有2个台阶那么小孩跳到这个台阶的方法有2种第一种从地面直接走到第二个台阶上第二种是小孩从地面走到第一个台阶再从第一个台阶走到第二个台阶上
假设现在有3个台阶那么小孩跳到这个台阶的方法有4种第一种直接跳到第三个台阶上第二种先跳到第一个台阶再从第一个台阶向第三个台阶跳而从第一个台阶向第三个台阶跳又有两种参考有2个台阶的方案那么总共第二种方法有2种第三种小孩跳到第二个台阶再从第二个台阶跳到第三个台阶因此总共有四种方法
假设现在有4个台阶那么小孩跳到第四个台阶的方法总共有7种先让小孩走到第一个台阶再从第一个台阶走到第四个台阶即可而小孩走到第一个台阶的方法有1种也可以先让小孩走到第二个台阶再从第二个台阶走到第四个台阶而小孩走到第二个台阶的方法有2种先让小孩走到第三个台阶再从第三个台阶直接到第四个台阶而直接让小孩走到第四个台阶的方法有4种因此上面的这些总计是7种
假设现在有5个台阶那么小孩跳到第五个台阶的方法有13种先让小孩跳到第二个台阶再从第二个台阶直接到第五个台阶…
因此规律就找到了其实就是一个斐波那契数列的变形问题利用上面的例题的思路就可以解决这个问题
class Solution
{
public:int waysToStep(int n) {vectorlong long dp(n4);dp[0]0;dp[1]1;dp[2]2;dp[3]4;for(int i4;in;i){dp[i]dp[i-1]dp[i-2]dp[i-3];dp[i] % 1000000007;}return dp[n];}
};使用最小花费爬楼梯 此题也是动态规划中的一个典型题这里从两个角度来看这道题
从最开始的介绍中可以知道对于动态规划的问题来说关键是dp[i]的意义和状态转移方程在解决问题的过程中要优先对这两个部分进行思考和解决那么两个不同的dp[i]的角度来看这个题
首先从第一个角度来看
如果这里的dp[i]表示的是上到第i个台阶需要花费多少钱 那么可以这样思考问题要知道上到第i个台阶需要多少钱就必然要知道上到第i-1个台阶要花多少钱再用这个钱加上上第i-1个台阶要花多少钱由于一次可以上两个台阶因此也要知道上到第i-2个台阶需要多少钱和上这个台阶需要多少钱再比较一下从第i-1个台阶上划算还是从第i-2个台阶上划算比较后就可以得到dp[i]的值因此状态转移方程就很容易得到了
dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2])此时注意一下边界初始化问题在第0和第1个台阶是不需要花钱的于是初始化为0即可代码也可以很好的实现出来
class Solution
{
public:int minCostClimbingStairs(vectorint cost) {vectorint dp(cost.size()1);dp[0]0;dp[1]0;for(int i2;icost.size();i){dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[cost.size()];}
};以上为第一种思考的方式dp[i]对应的意义还有其他这里还可以理解为从第i个位置上到最顶上需要的花费因此这里也可以借助这个意义来解决
那如果要求从第i个台阶上到顶端要花多少钱需要知道从第i个台阶一次上一个台阶还是一次上两个台阶比较划算因此这里又需要知道i1和i2的值根据这两个的值决定一次上一个台阶还是上两个台阶因此状态转移方程也可以得出来了
dp[i]min(dp[i1]cost[i],dp[i2]cost[i]);那么代码的实现也可以得出
class Solution
{
public:int minCostClimbingStairs(vectorint cost) {int ncost.size();vectorint dp(n);dp[n-1]cost[n-1];dp[n-2]cost[n-2];for(int in-3;i0;i--){dp[i]min(dp[i1]cost[i],dp[i2]cost[i]);}return min(dp[0],dp[1]);}
};
