一些可以用动态规划（DP）算法解决的问题（C++）_dp(m, vector(n) )

作者：寸_铁 | 2024-08-11 01:43:20

踩

dp(m, vector(n) )

一、动态规划问题

来源：暴力搜索->记忆式搜索->经典的动态规划->改进的动态规划。这也是动态规划问题的求解步骤。

本质：利用空间来换取时间。把一个问题分解为相同的子问题，这些子问题的求解是有顺序的，按顺序一步一步求解，前面的步骤和决策使得问题的状态转移到当前状态，当前状态再做出最优的决策，使问题转移到下一个状态，当问题进入最后一个状态时的解就是原问题的解。

二、练习题

1、有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。

解法（1）：按照经典的动态规划步骤进行，空间复杂度为O（n*aim）

 
  class  
  Exchange {

 
  public 
  :

 
       
  int  
  countWays(vector< 
  int 
  > penny,  
  int  
  n,  
  int  
  aim) {
    
 

 
  if  
  (penny.empty()||n ==  
  0 
  )

 
  return  
  0 
  ;

 
           
  vector<vector< 
  int 
  > > dp(n,vector< 
  int 
  >(aim+ 
  1 
  )); 
 

 
           
  for  
  ( 
  int  
  i =  
  0 
  ;i < n;i++) {
    
 

}

 
           
  for  
  ( 
  int  
  j =  
  1 
  ;j < aim+ 
  1 
  ;j++) {
    
 

 
               
  dp[ 
  0 
  ][j] = j%penny[ 
  0 
  ] ==  
  0 
  ? 
  1 
  : 
  0 
  ; 
 

}

 
           
  for  
  ( 
  int  
  i =  
  1 
  ;i < n;i++) {
    
 

 
               
  for  
  ( 
  int  
  j =  
  1 
  ;j < aim+ 
  1 
  ;j++) {
    
 

 
                   
  dp[i][j] = (j-penny[i]) >=  
  0 
  ?(dp[i- 
  1 
  ][j] + dp[i][j-penny[i]]):dp[i- 
  1 
  ][j];                    
 

}

}

 
  return  
  dp[n- 
  1 
  ][aim];

}

};

解法（2）：步骤与经典的动态规划问题一样，但是空间复杂度仅为O（aim）。其实在求dp矩阵时，都是根据上一行的值迭代出当前行的值，所以完全可以只用一维矩阵来存储，不断地更新一维矩阵即可。

 
  class  
  Exchange {

 
  public 
  :

 
       
  int  
  countWays(vector< 
  int 
  > penny,  
  int  
  n,  
  int  
  aim) {
    
 

 
           
  vector< 
  int 
  > dp(aim +  
  1 
  ); 
 

 
           
  for  
  ( 
  int  
  i =  
  0 
  ; i <= aim; i++) 
 

 
               
  if  
  (i % penny[ 
  0 
  ] ==  
  0 
  ) 
 

 
  dp[i] =  
  1 
  ;

 
           
  for  
  ( 
  int  
  i =  
  1 
  ; i < n; i++) 
 

 
  for  
  ( 
  int

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/寸_铁/article/detail/961535