对于题目的另外一种表述方式:
每个阶梯都有一定数量糖果,一次只能跨一个或者两个阶梯,走到一个阶梯就要吃光上面的糖果,问怎么走才能吃最少的糖果?开局你选前两个阶梯的其中一个作为开头点,并吃光该阶梯的糖果。
思路
当前吃掉的糖果数 ==当前阶梯上有的糖果数 + min(在前1阶时已吃糖果数, 在前2阶时,已吃糖果数);
利用min函数来选择已吃糖果数更少的阶梯,以达到状态转移。
dp[i]为台阶i上的糖果数
状态转移方程:dp[i] += min(dp[i-1], dp[i-2]);
class Solution { public: int minCostClimbingStairs(vector& cost) { int l = cost.size(); int dp[l+1]; dp[l] = 0;//注意这个值是cost没有赋予的,也就是顶楼的糖果数(0) for(int i = 0; i < l; i++) dp[i] = cost[i]; for(int i = 2; i <= l; i++) dp[i] += min(dp[i-1], dp[i-2]); return dp[l]; } };
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)