动态规划问题合集

1.数字三角形

#include <iostream> 
#include <algorithm>
using namespace std;


int main(int argc, char** argv) {
    int N,dp[100][100];
    cin>>N;
    for(int i=0;i<N;++i){
        for(int j=0;j<=i;++j){
            cin>>dp[i][j];
        }
    }
    for(int i=N-2;i>=0;--i){
        for(int j=0;j<=i;++j){
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+dp[i][j];
        }
    }
    cout<<dp[0][0];
    return 0;
}

---

2.最长上升子序列

#include <iostream> 
#include <algorithm>
#include <string.h>
using namespace std;


int main(int argc, char** argv) {
    int N,dp[1000],max_len=1,save[1000];
    fill(dp,dp+1000,1);
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>save[i];
    }
    for(int i=1;i<N;++i){
        for(int j=i-1;j>=0;--j){
            if(save[i]>save[j]){
                dp[i]=max(dp[j]+1,dp[i]);
                max_len=max(max_len,dp[i]);
            }
        }
    }
    cout<<max_len;
    return 0;
}

---

3.最长公共子序列

#include <iostream> 
#include <algorithm>
#include <string>
using namespace std;


int main(int argc, char** argv) {
    string a,b;
    cin>>a>>b;
    int dp[210][210];
    fill(dp[0],dp[0]+210*210,0);
    int max_len=0;
    int a_len=a.size(),b_len=b.size();
    for(int i=0;i<a_len;++i){
        for(int j=0;j<b_len;++j){
            if(a[i]==b[j]){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    cout<<dp[a_len-1][b_len-1];
    return 0;
}

---

4.Charm Bracelet

dp[j]表示大小为j的背包空间的最大价值

#include <iostream> 
#include <algorithm>
#include <string>
using namespace std;
struct bag{
    int w,v;
}bags[10000];

int main(int argc, char** argv) {
    int N,M;
    int dp[13000];
    fill(dp,dp+13000,0);
    cin>>N>>M;
    for(int i=1;i<=N;++i){
        cin>>bags[i].w>>bags[i].v;
    }
    for(int i=1;i<=N;++i){
        for(int j=M;j>=1;--j){
            if(j>=bags[i].w){
                dp[j]=max(dp[j],dp[j-bags[i].w]+bags[i].v);
            }
        }
    }
    cout<<dp[M];
    return 0;
}

---

5.滑雪

将山的高度从小到大排序
然后

#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
struct p{
    int x,y;
    int high;
};
vector<p> save;

bool cmp(p a,p b){
    return a.high<b.high;
}

int main(int argc, char** argv) {
    int hills[100][100],dp[100][100];
    int r,c,max_len=1;
    fill(hills[0],hills[0]+100*100,1);
    cin>>r>>c;
    for(int i=0;i<r;++i){
        for(int j=0;j<c;++j){
            cin>>hills[i][j];
            save.push_back({i,j,hills[i][j]});
        }
    }
    sort(save.begin(),save.end(),cmp);
    for(int i=0;i<save.size();++i){
        int x=save[i].x,y=save[i].y;
        for(int i=-1;i<=1;++i)
            for(int j=-1;j<=1;++j){
                if((i+j==1||i+j==-1)&&x+i>=0&&x+i<r&&y+j>=0&&y+j<c){
                    if(hills[x+i][y+j]<hills[x][y])
                    dp[x][y]=max(dp[x][y],hills[x+i][y+j]+1);
                }
            }
        max_len=max(dp[x][y],max_len);
    }
    cout<<max_len;
    return 0;
}

---