动态规划复习

àì夳堔傛蜴生んèń 2022-06-16 14:25 174阅读 0赞

1.动态规划之zhangjian老师滑雪

题目大意：滑雪智能从高处滑到低处，输出所有的滑雪路径上的最长的那条

代码实现：dp公式为dp\[i\]\[j\]=max(四个可以滑的方向的dp值)=max(maxn,dp\[i+movx\[t\]\]\[j+movy\[t\]\]);

#include <iostream>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    int movx[4]= {-1,0,1,0};
    int movy[4]= {0,1,0,-1};
    int r,c;
    int high[105][105];
    int dp[105][105];
    
    int fun(int i,int j)
    {
        int maxn=0;
        for(int t=0; t<4; t++)
        {
            int kx,ky;
            kx=i+movx[t];
            ky=j+movy[t];
            if(kx>=0 && kx<r && ky>=0 && ky<c && high[i][j]>high[kx][ky])
            {
                int k;
                if(dp[kx][ky]>0)
                {
                    k=dp[kx][ky];
                }
                else
                    k=fun(kx,ky);
                maxn=max(maxn,k);
            }
        }
        return maxn+1;
    }
    
    int main()
    {
        while(cin>>r>>c)
        {
            memset(high,0,sizeof(high));
            memset(dp,0,sizeof(dp));
            for(int i=0; i<r; i++)
            {
                for(int j=0; j<c; j++)
                {
                    cin>>high[i][j];
                }
            }
            for(int i=0; i<r; i++)
            {
                for(int j=0; j<c; j++)
                {
                    dp[i][j]=fun(i,j);
                }
            }
    
            int maxnn=0;
            for(int i=0; i<r; i++)
            {
                for(int j=0; j<c; j++)
                {
                    //cout<<dp[i][j]<<" ";
                    if(maxnn<dp[i][j])
                    {
                        maxnn=dp[i][j];
                    }
                }
                //cout<<endl;
            }
            cout<<maxnn<<endl;
    
        }
        return 0;
    }

2.带有负数的动态规划之步步惊心，二维

代码实现：

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    
    int main()
    {
        int m,n;
        int data[105][105];
        int dp[105][105];
        while(cin>>m>>n)
        {
            memset(data,0,sizeof(data));
            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    cin>>data[i][j];
                    dp[i][j]=-99999999;
                }
            }
            dp[m-1][0]=data[m-1][0];
            for(int j=1;j<n;j++)
            {
                dp[m-1][j]=dp[m-1][j-1]+data[m-1][j];
            }
            for(int i=m-2;i>=0;i--)
            {
                dp[i][0]=dp[i+1][0]+data[i][0];
            }
            for(int i=m-2;i>=0;i--)
            {
                for(int j=1;j<n;j++)
                {
                    dp[i][j]=max(dp[i][j-1],dp[i+1][j])+data[i][j];
                }
            }
            int maxn=-99999999;
            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(dp[i][j]>maxn)
                    {
                        maxn=dp[i][j];
                    }
                }
            }
            cout<<maxn<<endl;
        }
        return 0;
    }

3.最长上升子序列

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    
    int main()
    {
        int n;
        int data[1005];
        int dp[1005];
        while(cin>>n)
        {
            memset(data,0,sizeof(data));
            for(int i=0;i<n;i++)
            {
                cin>>data[i];
                dp[i]=1;///初始化为1，至少有一个数
            }
            for(int i=1;i<n;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if(data[i]>data[j])
                    {
                        dp[i]=max(dp[i],dp[j]+1);
                    }
                }
            }
            int maxn=-1;
            for(int i=0;i<n;i++)
            {
                if(dp[i]>maxn)
                    maxn=dp[i];
            }
            cout<<maxn<<endl;
    
        }
        return 0;
    }