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;
else
dp[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];
}
};
