本文主要是介绍代码随想录训练营Day38、39：Leetcode509、70、746、62、63，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Leetcode509：
问题描述：
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例 1：
输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
思路解析：
求第n个斐波那契数:f(n)=f(n-1)+f(n-2),只需要初始化f(0)=1,f(1)=1，后面的第n个数可以通过递推式循环求出
代码及注释：
1.非递归版
class Solution {
public:int fib(int n) {if(n<2)return n;//f(n-1) f(n)int num1=0,num2=1;int temp;for(int i=2;i<=n;i++){temp=num2;num2+=num1;num1=temp;}return num2;}
};2.递归版
class Solution {
public:int fib(int n) {if(n<2)return n;return fib(n-1)+fib(n-2);}
};Leetcode70：
问题描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
思路解析：
递推式为爬到第n层楼梯：f(n)=f(n-1)+f(n-2)
代码及注释：
class Solution {
public:int climbStairs(int n) {if(n<=2)return n;return climbStairs(n-1)+climbStairs(n-2);}
};Leetcode746：
问题描述：
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6 解释：你将从下标为 0 的台阶开始。 - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。 - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。 - 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。
思路解析：
分别求出从第0层开始走的最短花费f0(n)与从第1层开始走的最短花费f1(n)，return min(f0(n),f1(n));
f0(n)=min(f0[n-1]+cost[n-1],f0[n-2]+cost[n-2]);
代码及注释：
class Solution {
public:int f0[1005];int f1[1005];int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();f0[0]=0;f0[1]=cost[0];f1[1]=0;f1[2]=cost[1];for(int i=2;i<=n;i++){f0[i]=min(f0[i-1]+cost[i-1],f0[i-2]+cost[i-2]);}for(int i=3;i<=n;i++){f1[i]=min(f1[i-1]+cost[i-1],f1[i-2]+cost[i-2]);}return min(f0[n],f1[n]);}
};Leetcode62：
问题描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28
思路解析：
第一行的所有点走法只能有一种，第一列的所有点走法只能有一种，其余点位的走法为
dp[i][j]=dp[i-1][j]+dp[i][j-1]（i>1&&j>1）
代码及注释：
class Solution {
public:int dp[105][105];int uniquePaths(int m, int n) {for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(i==1||j==1)dp[i][j]=1;elsedp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m][n];}
};Leetcode63：
问题描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
思路解析：
特殊情况的处理，第一行存在dp[1][j]有障碍物时，后面的dp[1][j+i]（i>=0）都为0，无法到达。
第一列也是如此。当dp[i][j]（j>1&&i>1）时，该点无法到达，赋值为0;
代码及注释：
class Solution {
public:int dp[105][105];int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int n=obstacleGrid.size();int m=obstacleGrid[0].size();for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(obstacleGrid[i][j]==1){dp[i][j]=0;}else{if(i==0||j==0){if(i==0&&j==0)dp[i][j]=1;else if(i==0)dp[i][j]=dp[i][j-1];else dp[i][j]=dp[i-1][j];}else dp[i][j]=dp[i-1][j]+dp[i][j-1];}}}return dp[n-1][m-1];}
};这篇关于代码随想录训练营Day38、39：Leetcode509、70、746、62、63的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
