斐波那契数

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