【云上蓝桥·思特奇杯-算法集训营】第三周

【云上蓝桥·思特奇杯-算法集训营】第三周

斐波那契数

int fib(int n){
    int a1 = 1,a2 = 1,cur = 0;
    if(n == 1 | n == 2) return 1;
    for(int i = 2;i < n;i++)
    {
        cur = a1 + a2;
        a1 = a2;
        a2 = cur;
    }
    return cur;
}

第N个泰波那契数

class Solution {
public:
    int tribonacci(int n) {
        int res;
        int a = 0,b = 1,c = 1,temp = 0;
        if(n == 0) return a;
        if(n == 1) return b;
        if(n == 2) return c;
        for(int i = 3;i <= n;++i)
        {
            temp = a+b+c;
            a = b;
            b = c;
            c = temp;
        }
        return temp;
    }
};

爬楼梯

int climbStairs(int n){
    int method[n];
    if(n == 1||n == 2) return n;
    method[0] = 1;
    method[1] = 2;
    for(int i = 2;i < n;i++){
        method[i] = method[i - 1] + method[i - 2];
    }
    int target = method[n-1];
    return target;
}

 使用最小花费爬楼梯

#define MIN(x,y)  x < y ? x : y
int minCostClimbingStairs(int* cost, int costSize){
    int dp[costSize + 1],res;
    dp[0] = dp[1] = 0;
    for(int i = 2;i <= costSize;i++)
    {
        dp[i] = MIN(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
        res = dp[i];
    }
    return res;
}

买卖股票最佳时机

#define MIN(x,y) ((x) < (y)) ? (x) : (y)
int maxProfit(int* prices, int pricesSize){
    int date[pricesSize],min;
    date[0] = -prices[0],min = prices[0];
    for(int i = 1;i < pricesSize;i++){
        date[i] = prices[i] - min;
        min = MIN(min,prices[i]);
    }
    int profit = date[0];
    for(int i = 1;i < pricesSize;i++){
        if(date[i] > profit){
            profit = date[i];
        }
    }
    if(profit < 0) return 0;
    else return profit;
}

最长公共子序列（LCS） 

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len = fmax(text1.size(),text2.size());
        int dp[len+1][len+1];
        memset(dp,0,sizeof(dp));
        for(int i = 1;i <= text1.size();++i)
        {
            for(int j = 1;j <= text2.size();++j)
            {
                dp[i][j] = fmax(dp[i-1][j],dp[i][j-1]);
                if(text1[i-1] == text2[j-1])
                dp[i][j] = fmax(dp[i][j],dp[i-1][j-1] + 1);
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

节点选择

#include
#include
#include

using namespace std;
int dp[100002][2];
vector >v;
void dfs(int node,int pre)
{
   for(int i = 0;i < v[node].size();i++)
   {
       int temp = v[node][i];
       if(temp != pre)
       {
           dfs(temp,node);
           dp[node][1] += dp[temp][0];
           dp[node][0] += max(dp[temp][0],dp[temp][1]);
       }
   }
}
int main()
{
 int n;
 cin >> n;
 for(int i = 1;i <= n;i++)
 {
     cin >> dp[i][1];
 }
 int a,b;
 v.resize(n+1);
 for(int i = 1;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;
}

K好数

#include 
#include 
#include 
using namespace std;
int main()
{
    int k, l;
    cin >> k >> l;
    vector > dp(l+1, vector(k, 0));
    for(int i = 0; i < k;i++) dp[1][i] = 1;
    for(int i = 2; i <= l;i++)
    {
        for(int j = 0; j < k;j++)
        {
            int sum = 0;
            for(int m = 0; m < k;m++)
            {
                if(abs(m-j)!=1)  sum = (sum + dp[i - 1][m]) % 1000000007;
                dp[i][j] = sum;
            }
        }
    }
    int result = 0;
    for(int i = 1; i < k;i++)
    {
        result = (result + dp[l][i]) % 1000000007;
    }
    cout << result;
    return 0;
}