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

接下来就是一些常见的动态规划题目：

（1）

对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。

给定两个字符串A和B，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300，且三种代价值均小于等于100。

"abc",3,"adc",3,5,3,100

返回：8

    (1)当A[i-1]==B[j-1]时，说明（i，j）这个点的值，来自下面的三个方向（i-1，j)，(i,j-1)，(i-1,j-1)。如图：

   则dp[i][j]等于dp[i-1][j-1] ，dp[i-1][j]+c1，dp[i][j-1]+c0中的最小值

（2）A[i-1]!=B[j-1]时：

   则dp[i][j]等于dp[i-1][j-1] +c2，dp[i-1][j]+c1，dp[i][j-1]+c0中的最小值

程序：

int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {        vector
   
    
      > dp(n+1,vector
     
       (m+1,0));// write code here        dp[0][0] = 0;        for(int i=1;i
      
       < (dp[i][j-1]+c0) ? (dp[i-1][j]+c1) : (dp[i][j-1]+c0);                    dp[i][j] = min < (dp[i-1][j-1]+c2) ? min : (dp[i-1][j-1]+c2);                }            }        }        return dp[n][m];    }
      
     
    
   

  （2）

[1,4,2,5,3],5

返回：3

程序 int getLIS(vector
    
      A, int n) {        // write code here        vector
     
       dp(n,0);        dp[0]=1;           int len=1,i,j;        for(i=1;i
      
       A[j])                    dp[i]=max(dp[i],dp[j]);            }            dp[i]++;            len=max(len,dp[i]);        }        return len;    } （3）   
     
   一个背包有一定的承重cap，有N件物品，每件都有自己的价值，记录在数组v中，也都有自己的重量，记录在数组w中，每件物品只能选择要装入背包还是不装入背包，要求在不超过背包承重的前提下，选出物品的总价值最大。    
   给定物品的重量w价值v及物品数n和承重cap。请返回最大总价值。    
   
        测试样例：   
      
   [1,2,3],[1,2,3],3,6    
   返回：6 程序：   
    int maxValue(vector
       
         w, vector
        
          v, int n, int cap) {        // write code here        vector
         
           dp(cap+1,0); for(int i=0;i
          
           =w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } return dp[cap]; }
          
         
        
       
      
     
    

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