金昌网站seo,保定网站制作企业,广州响应式网站,myphoto wordpress 国外目录 509.斐波那契数
动态规划五部曲#xff1a; 1.确定dp数组#xff08;dp table#xff09;以及下标的含义 2.确定递推公式 3.dp数组如何初始化 4.确定遍历顺序 5.举例推导dp数组
70.爬楼梯
动态规划五部曲#xff1a; 1.确定dp数组#xff08;dp table#xff09;…目录 509.斐波那契数
动态规划五部曲 1.确定dp数组dp table以及下标的含义 2.确定递推公式 3.dp数组如何初始化 4.确定遍历顺序 5.举例推导dp数组
70.爬楼梯
动态规划五部曲 1.确定dp数组dp table以及下标的含义 2.确定递推公式 3.dp数组如何初始化 4.确定遍历顺序 5.举例推导dp数组
746.使用最小花费爬楼梯
动态规划五部曲 1.确定dp数组dp table以及下标的含义 2.确定递推公式 3.dp数组如何初始化 4.确定遍历顺序 5.举例推导dp数组 509.斐波那契数
题目链接509. 斐波那契数 - 力扣LeetCode
动态规划五部曲 1.确定dp数组dp table以及下标的含义 dp[i]表示第i项斐波那契数列 2.确定递推公式 第i项斐波那契数列 前两项之和即dp[i] dp[i-1] dp[i-2]; 3.dp数组如何初始化 递推公式的i 0和i 1不符合递推公式且是最边界情况特别处理 即dp[0] 0,dp[1] 1; 4.确定遍历顺序 从第三个数据位置开始遍历 5.举例推导dp数组 dp[2]、dp[3]符合递推到dp[...]都可行
class Solution
{
public:int fib(int n) {vectorint dp(n10);dp[0] 0;dp[1] 1;for(int i2; in; i){dp[i] dp[i-1] dp[i-2];}return dp[n];}
};
70.爬楼梯
题目链接70. 爬楼梯 - 力扣LeetCode
动态规划五部曲 1.确定dp数组dp table以及下标的含义 dp[i]表示第i个台阶的方案数 2.确定递推公式 1阶1 2阶2 3阶先走一步如果一步走一阶剩2阶方案数为2 如果一步走两阶剩1阶方案数为1方案数总共21 3 4阶先走一步如果一步走一阶剩3阶方案数为3 如果一步走两阶剩2阶方案数为2方案数总共32 5 5阶先走一步如果一步走一阶剩4阶方案数为5 如果一步走两阶剩3阶方案数为3方案数总共53 8 总结当前台阶i的方案数 i-1台阶方案数 i-2台阶方案数 即dp[i] dp[i-1] dp[i-2] 3.dp数组如何初始化 递推公式的i 1和i 2不符合递推公式且是最边界情况特别处理 即dp[1] 1,dp[2] 2; 4.确定遍历顺序 从第三个数据位置开始遍历 5.举例推导dp数组 第二步推到过了可行。
class Solution {
public:int climbStairs(int n) {vectorint dp(n10);dp[1] 1;dp[2] 2;for(int i3; in; i){dp[i] dp[i-1] dp[i-2]; // i-1台阶的方案数 i-2台阶的方案数 } return dp[n];}
};
746.使用最小花费爬楼梯
题目链接746. 使用最小花费爬楼梯 - 力扣LeetCode
动态规划五部曲 1.确定dp数组dp table以及下标的含义 dp[i]表示到达第i个台阶所花的最小费用 2.确定递推公式 0阶0元。 1阶0元。 2阶min(到达2-1阶的费用2-1阶跳的费用 到达2-2阶的费用 2-2阶跳的费用)。 3阶min(到达3-1阶的费用3-1阶跳的费用 到达3-2阶的费用 3-2阶跳的费用)。 4阶min(到达4-1阶的费用4-1阶跳的费用 到达4-2阶的费用 4-2阶跳的费用)。 整体看感觉思路可行即dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2])。 3.dp数组如何初始化 第0阶和第1阶的为起点不需要花费价钱故dp[0] 0, dp[1] 0。 4.确定遍历顺序 从第三个数据位置开始遍历 5.举例推导dp数组 按预期数据是从第0个台阶依次到第n个台阶顶点的变化所以数据是递推过去的担心min(可能取0的值验证了i 2的程序和i 3的清楚数据按预测的递推过程进行变化可行。
class Solution {
public:int minCostClimbingStairs(vectorint cost) {vectorint dp(cost.size()10);dp[0] 0;dp[1] 0;int n cost.size();for(int i2; in; i){// i-1往上爬 或者i-2往上爬取最小dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2]); // 通过这个输出题目信息把n改成了n了解到n-1是台阶而不是到顶// coutdp[i] dp[i-1]cost[i-1] dp[i-2]cost[i-2]\n; }return dp[n];}
};
