网站开发设计论文,昆明网站建设报价,江苏做网站价格,如何做漂亮的网站首页509. 斐波那契数
力扣题目链接(opens new window)
斐波那契数#xff0c;通常用 F(n) 表示#xff0c;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始#xff0c;后面的每一项数字都是前面两项数字的和。也就是#xff1a; F(0) 0#xff0c;F(1) 1 F(n) F(n -…509. 斐波那契数
力扣题目链接(opens new window)
斐波那契数通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是 F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1 给你n 请计算 F(n) 。
示例 1
输入2输出1解释F(2) F(1) F(0) 1 0 1
示例 2
输入3输出2解释F(3) F(2) F(1) 1 1 2
示例 3
输入4输出3解释F(4) F(3) F(2) 2 1 3
提示
0 n 30
动规五部曲
这里我们要用一个一维dp数组来保存递归的结果
确定dp数组以及下标的含义
dp[i]的定义为第i个数的斐波那契数值是dp[i]
确定递推公式
为什么这是一道非常简单的入门题目呢
因为题目已经把递推公式直接给我们了状态转移方程 dp[i] dp[i - 1] dp[i - 2];
dp数组如何初始化
题目中把如何初始化也直接给我们了如下
dp[0] 0;
dp[1] 1;确定遍历顺序
从递归公式dp[i] dp[i - 1] dp[i - 2];中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的
class Solution {public int fib(int n) {if (n 1) return n; int[] dp new int[n 1];dp[0] 0;dp[1] 1;for (int index 2; index n; index){dp[index] dp[index - 1] dp[index - 2];}return dp[n];}
}
70. 爬楼梯
力扣题目链接(opens new window)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。
示例 1
输入 2输出 2解释 有两种方法可以爬到楼顶。 1 阶 1 阶2 阶
示例 2
输入 3输出 3解释 有三种方法可以爬到楼顶。 1 阶 1 阶 1 阶1 阶 2 阶2 阶 1 阶 例如 第5阶楼梯是第3楼梯2和第四楼梯加1所以dp[i]dp[i-1]dp[i-2]
那么第一层楼梯再跨两步就到第三层 第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来那么就可以想到动态规划了。 746. 使用最小花费爬楼梯
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。 dp[i]的定义到达第i台阶所花费的最少体力为dp[i]。这道题其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。所以台阶一共有cost.length1个
可以有两个途径得到dp[i]一个是dp[i-1] 一个是dp[i-2]。
dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] cost[i - 1]。
dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] cost[i - 2]。
那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢
一定是选最小的所以dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]); // 方式一第一步不支付费用
class Solution {public int minCostClimbingStairs(int[] cost) {int len cost.length;int[] dp new int[len 1];// 从下标为 0 或下标为 1 的台阶开始因此支付费用为0dp[0] 0;dp[1] 0;// 计算到达每一层台阶的最小费用for (int i 2; i len; i) {dp[i] Math.min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}return dp[len];}
}
