【算法】- DP(动态规划)-白红宇的个人博客

【算法】- DP(动态规划)

发布日期：2022-02-10 08:11:05 浏览次数：12 分类：技术文章

本文共 2930 字，大约阅读时间需要 9 分钟。

动态规划大致的问题可以分为：

判断最长回文串

判断数字子串的和的最大

最长不下降子序列

最长公共子序列（LCS）

背包问题

A - Frog 1

#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;#define MAX 0x3f3f3f3ftypedef long long ll;int n,m,k;int dp[100001];//表示第i块石头最少的消耗int a[100001];int main(){ cin>>n; for(int i = 0 ; i < n ; i++) cin>>a[i]; dp[0] = 0; dp[1] = abs(a[1] - a[0]); for(int i = 2 ; i < n ; i++) dp[i] = min(dp[i-1] + abs(a[i] - a[i-1]), dp[i-2] + abs(a[i] - a[i-2])); cout<

B - Frog 2

#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;#define MAX 0x3f3f3f3ftypedef long long ll;int n,m,k;int dp[100001];//表示第i块石头最少的消耗int a[100001];int main(){ cin>>n>>k; for(int i = 0 ; i < n ; i++) cin>>a[i]; dp[0] = 0; dp[1] = abs(a[1] - a[0]); for(int i = 2 ; i < n ; i++){ int j; if(i >= k) j = i - k; else j = 0; int mmin = MAX; for(;j < i ; j++) mmin = min(mmin, dp[j] + abs(a[i] - a[j])); dp[i] = mmin; } cout<

C - Vacation

#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;#define MAX 0x3f3f3f3ftypedef long long ll;int n,m,k;struct Node{ int a,b,c;};Node node[100005];int dp[100005][5];//dp[i][j]表示第i天选第j个int main(){ cin>>n; for(int i = 0 ; i < n ; i++) scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c); dp[0][0] = node[0].a; dp[0][1] = node[0].b; dp[0][2] = node[0].c; for(int i = 1; i < n ; i++) { dp[i][0] += max(dp[i-1][1],dp[i-1][2]) + node[i].a; dp[i][1] += max(dp[i-1][0],dp[i-1][2]) + node[i].b; dp[i][2] += max(dp[i-1][0],dp[i-1][1]) + node[i].c; } cout<

D - Knapsack 1（0-1背包）

#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;#define MAX 0x3f3f3f3ftypedef long long ll;int n,m,k;ll dp[100001];ll w[100001];ll v[100001];int main(){ cin>>n>>k; for(int i = 0 ; i < n ; i++) cin>>w[i]>>v[i]; for(int i = 0 ; i 
               
                = w[i]; j--) dp[j] = max(dp[j],dp[j-w[i]] + v[i]); cout<

F - LCS （要求输出序列，要逆序DP）

#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;#define MAX 0x3f3f3f3ftypedef long long ll;int n,m,k;int dp[3001][3001];int main(){ string a,b; cin>>a>>b; int len1 = a.size(),len2 = b.size(); for(int i = len1 - 1; i >=0 ;i--) { for(int j = len2 - 1;j >= 0; 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]); } } int i=0; int j=0; while(i

转载地址：https://blog.csdn.net/qq_43567222/article/details/114633124 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：【深度学习】L1W2-python

下一篇：【深度学习】L1W2（2）- 用神经网络思想实现Logistic回归

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！