爬楼梯dp
class Solution {
public:
int climbStairs(int n) {
int dp[100];
dp[0]=dp[1]=1;
for(int i=2;i<=n;i++)
dp[i]=dp[i-1]+dp[i-2];
return dp[n];
}
};
class Solution {
public:
int tribonacci(int n) {
int dp[100];
dp[0]=0;
dp[1]=1;
dp[2]=1;
for(int i=3;i<=n;i++)
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
return dp[n];
}
};
class Solution {
public:
int search(vector<int>& nums, int target) {
for(int i=0;i<nums.size();i++)
{
if(nums[i]==target) return i;
}
return -1;
}
//
};
二分模板
//区间[l，r]被划分成[l,mid]和[mid + 1，r]时使用:
int bsearch_1(int 1, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; //判断mid是否满足性质
else l = mid + 1;
}
return l;
}
//区间[l,r]被划分成[l，mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
最后一步踏上第 n 阶，那么前一步应该就是在：
第 n-1 阶 或者 第 n-2 阶
所以：
踏上第 n 阶 的方法数 = 踏上第 n-1 阶的方法数 + 踏上第 n-2 阶的方法数
由此得到公式：
f(n) = f(n-1) + f(n-2)
这不就是个 肥boy纳妾(斐波那契) 的数列啊。