酒类营销网站,游戏网站搭建需要多少钱,绵阳网站建设哪家好,做家装图接单网站动态规划和我们数电中学习的时序电路类似#xff0c;某一时刻的状态不仅与当前时刻的输入有关#xff0c;还与之前的状态有关#xff0c;所以推导过程中我们需要模拟题目中的情况#xff0c;来找到每一时刻状态间的关系。 做题思路如下 509. 斐波那契数 此题简单 状态方程…动态规划和我们数电中学习的时序电路类似某一时刻的状态不仅与当前时刻的输入有关还与之前的状态有关所以推导过程中我们需要模拟题目中的情况来找到每一时刻状态间的关系。 做题思路如下 509. 斐波那契数 此题简单 状态方程为dp[i]dp[i-1]dp[2] 初始状态dp[0]0dp[1]1 class Solution {
public:int fib(int n) {if (n 1) return n;int dp[2]{0};dp[1]1;for (int i 2; i n; i){int tmp dp[0]dp[1];dp[0]dp[1];dp[1]tmp;}return dp[1];}
}; 70. 爬楼梯 仔细分析一下就会发现此题本质也是斐波那契数列 class Solution {
public:int climbStairs(int n) {if (n 2) return n;int dp[3] {0};dp[1]1;dp[2]2;for (int i 3; i n; i){dp[0] dp[1]dp[2];dp[1]dp[2];dp[2]dp[0];}return dp[2];}
}; 746. 使用最小花费爬楼梯 首先小于两层的楼梯可以看作是无花费的于是从第二层楼梯看起 因为求最小花费且每次都可爬一到两层 所以dp[i]min (dp[i-1]cost[i-1],dp[i-2]cost[i-2]) 由此找到关系写代码即可 class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorint dp(n1,0);for(int i 2; i n; i){dp[i] min (dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[n];}
};
