织梦网站如何做软件下载,公司网站建设济南,建网站的流程和费用,wordpress怎么修改关键词1137. 第 N 个泰波那契数
题目描述#xff1a; 状态表示: dp[i]表示第i个泰波那契数。 状态转移方程#xff1a; dp[i]dp[i-3]dp[i-2]dp[i-1]。 初始化: 动态规划问题的初始化就是为了去避免初始情况下的越界问题。这里就对dp[0]0,dp[1]1,dp[2]1这样进行初始化即可#xf…1137. 第 N 个泰波那契数
题目描述 状态表示: dp[i]表示第i个泰波那契数。 状态转移方程 dp[i]dp[i-3]dp[i-2]dp[i-1]。 初始化: 动态规划问题的初始化就是为了去避免初始情况下的越界问题。这里就对dp[0]0,dp[1]1,dp[2]1这样进行初始化即可题目已经给出了非常简单。 填表顺序: 显而易见填表顺序为从左到右。 返回值: 因为dp[i]表示第i个泰波那契数题目要求计算第n个斐波那契数因此返回dp[n]即可。 代码如下: 经过以上过程之后编写代码还要注意一个细节注意要提前根据n的大小进行判断如果数组大小小于等于2但是未经过判断后面的初始化就会出现越界问题。
class Solution {public int tribonacci(int n) {int[] dp new int[n 1];if (n 0) {return 0;}if (n 1) {return 1;}if (n 2) {return 1;}dp[0] 0;dp[1] 1;dp[2] 1;for (int i 3; i n; i) {dp[i] dp[i - 3] dp[i - 2] dp[i - 1];}return dp[n];}
}
题目链接 时间复杂度:O(n) 空间复杂度:O(n) 空间优化版本
class Solution {public int tribonacci(int n) {if (n 0) {return 0;}if (n 1) {return 1;}if (n 2) {return 1;}int num1 0;int num2 1;int num3 1;int num4 0;for (int i 0; i n - 3; i) {num4 num1 num2 num3;num1 num2;num2 num3;num3 num4;}return num3;}
}面试题 08.01. 三步问题
题目描述: 状态表示 dp[i]表示达到第i阶台阶有多少种方法。 状态转移方程 dp[i]dp[i-1]dp[i-2]dp[i-3]。 初始化 还是为了防止越界初始化dp[1]0,dp[2]2,dp[0]1。 填表顺序 从左至右。 返回值 返回dp[n]。 代码如下
class Solution {public int waysToStep(int n) {int[] dp new int[n 1];if (n 0 || n 1) {return 1;}if (n 2) {return 2;}dp[0] 1;dp[1] 1;dp[2] 2;int MOD (int) 1e9 7;for (int i 3; i n; i) {dp[i] ((dp[i - 1] dp[i - 2]) % MOD dp[i - 3]) % MOD;}return dp[n];}
}题目链接 时间复杂度:O(n) 空间复杂度:O(n)
746. 使用最小花费爬楼梯
题目描述: 状态表示: 第一种方法dp[i]表示到达第i个台阶使用的最低费用。 第二种方法dp[i]表示从第i个台阶到达最顶部的最低费用。 状态转移方程: dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2])。 dp[i]min(dp[i1]dp[i2])cost[i]。 初始化 方法一要避免越界初始化dp[0]0,dp[1]0。 方法二要避免越界初始化dp[n-1]cost[i],dp[n]0。 填表顺序: 方法一从左至右方法二从右至左。 返回值: 方法一返回值为dp[n]这里的n是cost数组的长度。 方法二返回值为min(dp[0],dp[1])。 方法一代码如下:
class Solution {public int minCostClimbingStairs(int[] cost) {int n cost.length;int[] dp new int[n 1];for (int i 2; i n; i) {dp[i] Math.min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}return dp[n];}}方法二代码如下
class Solution {public int minCostClimbingStairs(int[] cost) {int n cost.length;int[] dp new int[n 1];dp[n] 0;dp[n - 1] cost[n - 1];for (int i n - 2; i 0; i--) {dp[i] Math.min(dp[i 1], dp[i 2]) cost[i];}return Math.min(dp[0], dp[1]);}}题目链接 方法一和方法二的时空复杂度相同如下 时间复杂度:O(n) 空间复杂度:O(n)
