斐波那契数
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; }
