棋牌网站开发需要多少钱,整网站代码 带数据 免费 下载,wordpress充值会员插件,商务网站建设管理思路语言
Java
509. 斐波那契数
斐波那契数
题目
斐波那契数 #xff08;通常用 F(n) 表示#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始#xff0c;后面的每一项数字都是前面两项数字的和。也就是#xff1a;
F(0) 0#xff0c;F(1) 1
F(n) F(n -…语言
Java
509. 斐波那契数
斐波那契数
题目
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(1) 1
F(n) F(n - 1) F(n - 2)其中 n 1给定 n 请计算 F(n) 。 思路
动态规划五部曲
1.明白dp数组下标的含义
2.初始化
3.确定递推公式有时候初始化要跟着递推公式来。
4.确定遍历顺序
5.举例推导dp数组
代码
标准版
class Solution {public int fib(int n) {//动规五部曲if (n 2) return n;int[] dp new int[n 1];//明白dp数组下标含义dp[0] 0;//初始化dp[1] 1;for (int i 2; i n; i) {//确定遍历顺序dp[i] dp[i -1] dp[i - 2];//递推公式}return dp[n];//举例推导递推数组}
}
精简版
class Solution {public int fib(int n) {if (n 2) return n;int a 0;int b 1;int c 0;for (int i 2; i n; i) {c a b; a b;b c;}return c;}
}
易错点
数组定义大小的时候是n 1因为索引从零开始。
遍历的时候从2开始从n结束。
70. 爬楼梯
爬楼梯
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 思路
动规五部曲
数组dp[i]代表的含义代表第i阶的时候有dp[i]种方法。
初始化将0和1索引位置都设为1这样2的时候才有两种方法。
递推公式从前面两次方法数相加就是本次方法的数量。
遍历顺序从前到后
举例推导dp数组。
代码
class Solution {public int climbStairs(int n) {int[] dp new int[n 1];dp[0] 1;dp[1] 1;for (int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}
易错点
索引为0的时候数值为1.
746. 使用最小花费爬楼梯
使用最小花费爬楼梯
题目
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。 思路
动规五部曲
dp数组i位置的含义在索引为I时花费最少的钱。
递推公式目前索引花费最少的钱等于前一个索引花费最少的钱和前一个索引带来带来的消耗与前面第二索引带来的进行比较取最少的。文字可能有点晦涩难懂具体看代码。
初始值因为在0或1的位置都不动只有跳了才有消耗所以是0.
遍历正序遍历
推导dp数组用IDEA打印出来看看与结果有什么不同发现错误就进行debug
代码
class Solution {public int minCostClimbingStairs(int[] cost) {int len cost.length;int[] dp new int[len 1];dp[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];}
}
易错点
明白递推公式的含义。
总结
今天是动态规划的第一天继续加油不断完善自己。
锲而不舍金石可镂
