您现在的位置是：首页 >技术杂谈 >算法笔记2.12-＞动态规划网站首页技术杂谈

Fibonacci

#include <bits/stdc++.h>
using namespace std;
const int maxn=31;
int dp[maxn];

int F(int n){
    if(n==0||n==1) return 1;
    if(dp[n]!=-1) return dp[n];
    else{
        dp[n]=F(n-1)+F(n-2);
        return dp[n];
    }
}

int main() {
    int n;
    while(cin>>n){
        fill(dp,dp+maxn,-1);
        int ans=F(n);
        cout<<ans<<endl;
    }
    return 0;
}

最大连续子序列

#include <bits/stdc++.h>
using namespace std;
const int maxn=10010;
int A[maxn];
struct dpNode{
    int data;
    int st;
    int ed;
}dp[maxn];

void getDp(int n){
    dp[0].data=A[0];
    dp[0].st=0;
    dp[0].ed=0;
    for (int i = 1; i < n; ++i) {
        if(dp[i-1].data+A[i]>A[i]){
            dp[i].data=dp[i-1].data+A[i];
            dp[i].st=dp[i-1].st;
            dp[i].ed=i;
        }else{
            dp[i].data=A[i];
            dp[i].st=i;
            dp[i].ed=i;
        }
    }
}

int main() {
    int n;
    while(cin>>n&&n!=0){
        int count=0;
        for (int i = 0; i < n; ++i) {
            cin>>A[i];
            if(A[i]<0) count++;
        }
        if(count==n) {
            cout<<'0'<<' '<<A[0]<<' '<<A[n-1]<<endl;
            continue;
        }
        getDp(n);
        int k=0,maxdata=dp[0].data;
        for (int i = 1; i < n; ++i) {
            if(dp[i].data>maxdata){
                maxdata=dp[i].data;
                k=i;
            }
        }
        cout<<dp[k].data<<' '<<A[dp[k].st]<<' '<<A[dp[k].ed]<<endl;
    }
    return 0;
}

最长上升子序列

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000;
int A[maxn],dp[maxn];

int main() {
    int n;
    cin>>n;
    for (int i = 1; i <= n; ++i) {
        cin>>A[i];
    }
    int ans=-1;
    for (int i = 1; i <=n; ++i) {
        dp[i]=1;
        for (int j = 1; j <i; ++j) {
            if(A[i]>A[j]&&dp[j]+1>dp[i]){
                dp[i]=dp[j]+1;
            }
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

最长公共子序列

#include <bits/stdc++.h>
using namespace std;
const int maxn=110;

int lcs(string s1,string s2){
    int m=s1.size();
    int n=s2.size();
    int dp[m+1][n+1];
    for (int i = 0; i <=m; ++i) {
        for (int j = 0; j <=n; ++j) {
            if(i==0||j==0) dp[i][j]=0;
            else if(s1[i-1]==s2[j-1]){
                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];
}

int main() {
    string s1,s2;
    while(cin>>s1>>s2){
        cout<<lcs(s1,s2)<<endl;
    }
    return 0;
}

最长回文子串

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
string s1, s;
int dp[maxn][maxn];

string filterS(string &s) {
    string res;
    for (char c : s) {
        if (isalpha(c)) {
            res += toupper(c);
        }
    }
    return res;
}

int main() {
    getline(cin, s1);
    s = filterS(s1);
    int len = s.length(), ans = 1, start = 0;
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < len; ++i) {
        dp[i][i] = 1;
        if (i < len - 1) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = 1;
                start = i;
                ans = 2;
            }
        }
    }
    for (int l = 3; l <= len; l++) {
        for (int i = 0; i + l - 1 < len; ++i) {
            int j = i + l - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1] == 1) {
                dp[i][j] = 1;
                start = i;
                ans = l;
            }
        }
    }
    int oristart = 0, index = 0,oriend=0;
    for (int i = 0; i < s1.length(); ++i) {
        if (isalpha(s1[i])) {
            if (index == start) {
                oristart = i;
            }
            if (index == start+ans-1) {
                oriend = i;
            }
            index++;
        }
    }
    cout << s1.substr(oristart,oriend-oristart+1) << endl;
    return 0;
}