代码随想录33|509. 斐波那契数，70. 爬楼梯，746. 使用最小花费爬楼梯， 34. 在排序数组中查找元素的第一个和最后一个位置

509. 斐波那契数

链接地址

class Solution {
public:int fib(int n) {if (n <= 1) return n;vector<int> dp(n + 1);dp[0] = 0;dp[1] = 1;for (int i = 2; i < n + 1; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

70. 爬楼梯

链接地址

class Solution {
public:int climbStairs(int n) {if (n <= 1) return n;vector<int> dp(n + 1);dp[1] = 1;dp[2] = 2;for (int i = 3; i < n + 1; i++) {dp[i] = dp[i -1] + dp[i - 2];}return dp[n];}
};

746. 使用最小花费爬楼梯

链接地址

class Solution {
public:int climbStairs(int n) {if (n <= 1) return n;vector<int> dp(n + 1);dp[1] = 1;dp[2] = 2;for (int i = 3; i < n + 1; i++) {dp[i] = dp[i -1] + dp[i - 2];}return dp[n];}
};

附加复习二分题：

34. 在排序数组中查找元素的第一个和最后一个位置

代码思路：使用二分查找法，找到目标值的位置，然后左右扩散去寻找元素的左右边界。

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int leftResult = -1;int rightResult = -1;vector<int> result;int left = 0;int right = (nums.size() - 1);while (left <= right) {int mid = left + (right - left) / 2;     if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] < target) {left = mid + 1;} else {int flag = mid;while (flag >= 0 && nums[flag] == target) {flag--;}leftResult = flag + 1;while (mid < nums.size() && nums[mid] == target) {mid++;}rightResult = mid - 1;break;}}result.push_back(leftResult);result.push_back(rightResult);return result;}
};