seo优化网站技术排名百度推广,临沂网站建设怎么样,微信公众平台怎么登录,微信小程序开发哪家好Day38 动态规划
又开始了新的章节#xff0c;有了点难度的感觉。。 动态规划五部曲#xff1a; 确定dp数组#xff08;dp table#xff09;以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组 这些以后慢慢参透
LeetCode 509.斐波纳契数
最简单…Day38 动态规划
又开始了新的章节有了点难度的感觉。。 动态规划五部曲 确定dp数组dp table以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组 这些以后慢慢参透
LeetCode 509.斐波纳契数
最简单的动态规划甚至不需要动态规划就可以解决的问题。初始状态、递推公式都已经有了这道题就很简单了。
class Solution {
public:int fib(int n) {if(n1) return n;vectorint dp(n1);dp[0]0;dp[1]1;for(int i2;in;i)dp[i]dp[i-1]dp[i-2];return dp[n];}
};LeetCode 76.爬楼梯
爬楼梯的关键是递推公式的推导如果能推导出来每一层是由前两层走上来的那么这道题几乎就是一个变种的斐波纳契数列了。
class Solution {
public:int climbStairs(int n) {if(n1) return n;vectorint dp(n1);dp[1]1;dp[2]2;for(int i3;in;i)dp[i]dp[i-1]dp[i-2];return dp[n];}
};LeetCode 746. 使用最小花费爬楼梯
dp数组的含义到达i位置的花费为dp[i] 递推公式dp[i-1]cost[i-1]和dp[i-2]cost[i-2]的最小值 初始化dp[0]dp[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()];}
};动态规划继续加油
