《九日集训》第十三轮（第三讲) 一维数组

Question

爬楼梯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];

    }
};

. 第 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];

    }
};

33. 搜索旋转排序数组

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;
    }
   //
};

81. 搜索旋转排序数组 II

153. 寻找旋转排序数组中的最小值

 

二分模板

//区间[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;
}
 

 

 

Answer 1

最后一步踏上第 n 阶，那么前一步应该就是在：
第 n-1 阶 或者 第 n-2 阶
所以：
踏上第 n 阶 的方法数 = 踏上第 n-1 阶的方法数 + 踏上第 n-2 阶的方法数
由此得到公式：
f(n) = f(n-1) + f(n-2)
这不就是个 肥boy纳妾(斐波那契) 的数列啊。