网站域名能迁移吗,天津公司网站怎样制作,百度推广效果怎么样,管理咨询公司名称大全个人主页 #xff1a; zxctscl 如有转载请先通知 题目 1. 前言2. 1137第 N 个泰波那契数2.1 分析2.2 代码 3. 面试题 08.01. 三步问题3.1 分析3.2 代码 4. 746使用最小花费爬楼梯4.1 分析4.1.1 以i位置为终点4.1.2 以i位置为起点 4.2 代码4.2.1以i位置为终点4.2.2以i位置为起点… 个人主页 zxctscl 如有转载请先通知 题目 1. 前言2. 1137第 N 个泰波那契数2.1 分析2.2 代码 3. 面试题 08.01. 三步问题3.1 分析3.2 代码 4. 746使用最小花费爬楼梯4.1 分析4.1.1 以i位置为终点4.1.2 以i位置为起点 4.2 代码4.2.1以i位置为终点4.2.2以i位置为起点 1. 前言
做动态规划的题目有个固定的模式1.状态表示2.状态转移方程3.初始化4.填表顺序5.确定返回值。
2. 1137第 N 个泰波那契数 2.1 分析
先根据题目要求先创建dp表vectorint dp(n1) 再根据题目已给的定义初始化 dp[0]0;dp[1]dp[2]1; 在循环里面根据题目已给的公式写出循环 dp[i]dp[i-1]dp[i-2]dp[i-3]; 最后返回得到的结果return dp[n]; 这里考虑到可能会越界就得先加一个判断
if(n0) return 0;
if(n1||n2) return 1;这个代码空间复杂度为O(n)优化一下代码将空间复杂度降到O(1)。 写出几项就会发现将设置的几个变量连续赋值就能达到滚动的效果。将b的值先赋给a,在c的值先赋给b,d的值先赋给c。就这样一直到n最后返回d的值就行。
2.2 代码
class Solution {
public:int tribonacci(int n) {if(n0) return 0;if(n1||n2) return 1;vectorint dp(n1);dp[0]0;dp[1]dp[2]1;for(int i3;in;i){dp[i]dp[i-1]dp[i-2]dp[i-3];}return dp[n];}
};优化空间后的代码:
class Solution {
public:int tribonacci(int n) {if(n0) return 0;if(n1||n2) return 1;int a0,b1,c1, d0;for(int i3;in;i){dabc;ab;bc;cd;}return d; }
};3. 面试题 08.01. 三步问题 3.1 分析
假设要到第4个台阶就可以从第3个台阶到第4个台阶也可以从第2个台阶到第4个台阶还可以从第1个台阶到到第4个台阶总的到第第4个台阶的方法也就是上面加的和。 而到第一个台阶就有1种。 到第2个台阶可以先到1也可以直接到2就有两种方法。 到第3个台阶可以直接到也可以从1到还可以从2到。而到2的方法有两种。所以到3的方法就有4种。
那么很显然要到第i个台阶知道到第i-1和i-2和i-3有多少种就可以了
dp[i]dp[i-1]dp[i-2]dp[i-3]要先考虑越界的问题就先判断一下 if(n1||n2)return n;if(n3)return 4;题目还要求取模就直接定义一个int const Mod1e97;用来取模。 最后返回return dp[n];就行。
3.2 代码
class Solution {
public:int waysToStep(int n) {int const Mod1e97;if(n1||n2)return n;if(n3)return 4;vectorint dp(n1);dp[1]1;dp[2]2;dp[3]4;for(int i4;in;i){dp[i]((dp[i-1]dp[i-2])%Moddp[i-3])%Mod;}return dp[n];}
};4. 746使用最小花费爬楼梯 4.1 分析
这里得先明白到达楼梯顶部不是这里顺序表的长度而是长度再加1。
4.1.1 以i位置为终点
以i位置为终点 要知道到达第i个台阶就得先到达第i-1或者第i-2个台阶这里选择的是对应花费最小的那一个再加上它对应dp表所对应的值
dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2])在初始化的时候题目已经给出可以下标为 0 或下标为 1 的台阶开始爬楼梯那么他们对应的花费就为0
dp[0]dp[1]0;最后返回最小花费 return dp[cost.size()];4.1.2 以i位置为起点
dp[i]表示从i位置出发到达楼顶此时的最小花费。 以第i个台阶为起点就得先到达第i1或者第i2个台阶看一下到达哪个台阶对应的花费低就到达哪一个台阶。
dp[i]min(dp[i1],dp[i2])cost[i];此时初始化的位置就是n-1和n-2 dp[n-1]cost[n-1];dp[n-2]cost[n-2];最后返回的结果是0和1位置的最小值
return min(dp[0],dp[1]);4.2 代码
4.2.1以i位置为终点
class Solution {
public:int minCostClimbingStairs(vectorint cost) {vectorint dp(cost.size()1);dp[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()];}
};4.2.2以i位置为起点
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int ncost.size();vectorint dp(n);dp[n-1]cost[n-1];dp[n-2]cost[n-2];for(int in-3;i0;i--){dp[i]min(dp[i1],dp[i2])cost[i];}return min(dp[0],dp[1]);}
};有问题请指出大家一起进步!
