江苏海宏建设工程有限公司网站,农村小工厂暴利,小学生收集的新闻10条,淄博平台公司第三十二天打卡#xff0c;动态规范第一天#xff01;今天比较简单#xff0c;主要理解dp的概念 509.斐波那契数列
题目链接
解题过程
状态转移方程 dp[i] dp[i - 1] dp[i - 2];
动态规划
class Solution {
public:int fib(int n) {if (n 2) return n;int dp[n …第三十二天打卡动态规范第一天今天比较简单主要理解dp的概念 509.斐波那契数列
题目链接
解题过程
状态转移方程 dp[i] dp[i - 1] dp[i - 2];
动态规划
class Solution {
public:int fib(int n) {if (n 2) return n;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];}
};70.爬楼梯
题目链接
解题过程
第三层楼梯的状态可以由第二层楼梯和到第一层楼梯状态推导出来即爬到第三层楼的方法数等于爬到第二层楼的方法数与爬到第一层楼的方法数之和
动态规划
class Solution {
public:int climbStairs(int n) {if (n 2) return n;vectorintdp(n 1);dp[1] 1;dp[2] 2;for (int i 3; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp.back();}
};746.使用最小花费爬楼梯
题目链接
解题过程 dp[i]的定义到达第i台阶所花费的最少体力为dp[i]。 dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] cost[i - 1]。 dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] cost[i - 2]。
动态规划
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int len cost.size();vectorintdp(len 1);dp[0] 0;dp[1] 0;for (int i 2; i len; i) {dp[i] min(cost[i - 2] dp[i - 2], cost[i - 1] dp[i - 1]);}return dp.back();}
};
