前言
我生来平平淡淡，没有显赫家世，没有倾城面貌。惊艳不了青春，斑驳不了岁月。可我依然想温暖时光，饱读诗书，努力弥补我这平淡出生，后期绚烂绽放。
理论基础：
动规五部曲：
1、数组定义
2、递推公式
3、数组初始化
4、遍历顺序
5、打印数组
一、 斐波那契数
谁又能想到这是一道动态规划类题目呢。
解题思路：
数组定义：就单纯是一个数。
递推公式：dp[i]=dp[i-1]+dp[i-2]
遍历顺序：从前往后，这样才能吃到结果。
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]; } };
二、爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢。
解题思路：
一次只能上1或2个台阶，这一个台阶的方法取决于前一个和前两个的台阶的方法。
class Solution { public: int climbStairs(int n) { if(n<=2) { return n; } vector<int> dp(n+1); dp[1]=1; //第一阶1钟，第二阶2种，然后就可以递推下去 dp[2]=2; for(int i=3;i<=n;i++) { dp[i]=dp[i-1]+dp[i-2]; //递推 } return dp[n]; } };
三、使用最小花费爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
解题思路：
dp代表来到这级台阶的花销，cost是跳起来的花销。
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { if(cost.size()==2) { return cost[0]<cost[1]?cost[0]:cost[1]; } vector<int> dp(cost.size()+1); //花费 dp[0]=0; //一开始不用 dp[1]=0; for(int i=2;i<=cost.size();i++) { dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); //哪一种花销最低 } return dp[cost.size()]; } };
总结
继续冲！！！
