斐波那契数 #

class Solution {
public:
    int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
};

第 N 个泰波那契数 #

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        int p = 0, q = 0, r = 1, s = 1;
        for (int i = 3; i <= n; ++i) {
            p = q;
            q = r;
            r = s;
            s = p + q + r;
        }
        return s;
    }
};

爬楼梯 #

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
};

使用最小花费爬楼梯 #

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
};

买卖股票的最佳时机 #

class Solution
{
public:
    int max(int x, int y)
    {
        return x > y ? x : y;
    }
    int maxProfit(vector<int> &prices)
    {
        if(prices.size()==1)
            return 0;
        int low_price = prices[0];
        prices[0] = 0;
        for (int i = 1; i < prices.size(); i++)
        {
            low_price = low_price > prices[i] ? prices[i] : low_price;
            if (prices[i] > low_price)
                prices[i] = max(prices[i - 1], prices[i] - low_price);
            else
                prices[i] = prices[i - 1];
        }
        return prices.back();
    }
};

最长公共子序列 #

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
            char c1 = text1.at(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.at(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

杨辉三角形 #

节点选择 #

#include<bits/stdc++.h>

using namespace std;

vector<vector<int> > v;//存放树形结构

int dp[100005][2] = {0};

void dfs(int a, int pre){
	for(int i = 0; i < v[a].size(); i++){
		int t = v[a][i];
		if(t != pre){//只要不是相邻节点就符合题意
			dfs(t, a);
			dp[a][0] += max(dp[t][0], dp[t][1]);//不选择该节点，保存下一节点的最大值
			dp[a][1] += dp[t][0];//选择该节点，下一节点只能不选择
		}
	}
}
int main(){
	int n, a, b;
	cin >> n;
	v.resize(n + 1);//给定数据大小
	for(int i = 1; i <= n; i ++)
		cin >> dp[i][1];//输入节点的权重
	for(int i = 0; i < n-1; i ++){
		cin >> a >> b;//输入节点之间的关系
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1, 0);
	cout << max(dp[1][0], dp[1][1]) << endl;
	return 0;
}

耐摔指数 #

#include<bits/stdc++.h>
using namespace std;
int f2[105],f3[105];
int main(){
	int n;
	while(~scanf("%d",&n)){
		int i=0;
		while(f3[i]<n){
			i++;
			f2[i]=f2[i-1]+i;
			f3[i]=f3[i-1]+f2[i-1]+1;
		}
		cout<<i<<endl;
	}
	return 0;

k 好数 #

#include <iostream>
#include <cmath>
using namespace std;
#define MOD 1000000007
//L位K进制
void Count(int length,int range){
	long long int dp[110][110],sum=0;
	for(int j=0;j<100;j++)
		dp[0][j]=1;
	for(int i=1;i<length;i++){
		for(int j=0;j<range;j++){
			for(int k=0;k<range;k++){
				if(abs(j-k)!=1){		//判断不是相邻位
					if(i==length-1 && j==0)  //当i为数的最高位时不能为0
						continue;
					dp[i][j]=dp[i][j]+dp[i-1][k];
					dp[i][j]%=MOD;
				}
			}
		}
	}
	for(int i=0;i<range;i++){
		sum+=dp[length-1][i];
		sum%=MOD;
	}
	cout<<sum;
}
int main() {
	int k,l;
	cin>>k>>l;
	if(k==1 && l==1)	cout<<0;
	else if(k>1 && l==1)
			cout<<k;
	else if(l>1)
			Count(l,k);
	return 0;
}