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

C++动态规划学习与实践

动态规划题目特点

动态规划是一种解决复杂问题的强大工具，常用于计算机科学和工程领域。以下是动态规划题目的典型特点：

动态规划步骤

动态规划的核心步骤包括：

动态规划代码示例

1. Coin Change（硬币问题）

问题：给定不同面值的硬币和一个总金额，求最少需要多少枚硬币才能凑出该金额。

示例代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int coinChange(vector
       
         coins, int amount) {    vector
        
          dp(amount + 1, INT_MAX); dp[0] = 0; for (int i = 1; i <= amount; ++i) { for (int j = 0; j < coins.size(); ++j) { if (i >= coins[j] && dp[i - coins[j]] != INT_MAX) { dp[i] = min(dp[i], dp[i - coins[j]] + 1); } } } return dp[amount] != INT_MAX ? dp[amount] : -1;}int main() { vector
         
           coins; int temp; while (cin >> temp && getchar() != '\n') { coins.push_back(temp); } coins.push_back(temp); int amount; cin >> amount; cout << coinChange(coins, amount); return 0;}
         
        
       
      
     
    
   

分析：代码中使用动态规划数组dp来记录最少硬币数量。从左到右依次计算每个金额，确保计算顺序正确。

2. Unique Paths（路径计数问题）

问题：计算从左上角走到右下角的不同路径数量。

示例代码：

#include 
   
    #include 
    
     using namespace std;int uniquePaths(int m, int n) {    vector
     
      
       > dp(m, vector
       
        (n, 0));    for (int i = 0; i < m; ++i) {        for (int j = 0; j < n; ++j) {            if (i == 0 && j == 0) {                dp[i][j] = 1;            } else if (i == 0 || j == 0) {                dp[i][j] = 1;            } else {                dp[i][j] = dp[i-1][j] + dp[i][j-1];            }        }    }    return dp[m-1][n-1];}int main() {    int m, n;    cin >> m >> n;    cout << uniquePaths(m, n);    return 0;}
       
      
     
    
   

分析：代码中使用二维数组dp记录路径数量。从左上角开始，逐步计算每个格子的路径数量。

3. Jump Game（跳游戏问题）

问题：判断青蛙是否能从起始点跳到终点。

示例代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;bool canJump(vector
       
         a) {    int n = a.size();    vector
        
          dp(n, false); dp[0] = true; for (int j = 1; j < n; ++j) { for (int i = 0; i < j; ++i) { if (dp[i] && i + a[i] >= j) { dp[j] = true; break; } } } return dp[n-1];}int main() { vector
         
           a; int temp; while (cin >> temp && getchar() != '\n') { a.push_back(temp); } a.push_back(temp); cout << canJump(a) ? "True" : "False"; return 0;}
         
        
       
      
     
    
   

分析：代码中使用动态规划数组dp记录能否到达每个石头位置。从左到右依次判断是否能跳到下一个石头。

4. Maximum Product Subarray（最大子数组乘积）

问题：找到数组中最大的连续子数组的乘积。

示例代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int MaxProductSubarray(const vector
       
        & a) {    if (a.empty()) return 0;    vector
        
          dp(a.size(), 0); dp[0] = a[0]; int maxn = dp[0]; for (int i = 1; i < a.size(); ++i) { dp[i] = max(dp[i-1] * a[i], a[i]); maxn = max(maxn, dp[i]); } return maxn;}int main() { vector
         
           a; int temp; while (cin >> temp && getchar() != '\n') { a.push_back(temp); } a.push_back(temp); cout << MaxProductSubarray(a); return 0;}
         
        
       
      
     
    
   

分析：代码中使用动态规划数组dp记录当前子数组的最大乘积。从左到右依次计算每个元素的最大乘积。

总结

动态规划是一种强大的算法设计方法，通过将复杂问题分解为更小的子问题并通过状态转移求解，最终得到最优解。以上代码示例展示了动态规划在不同问题中的应用场景，理解这些代码可以帮助更好地掌握动态规划的原理和实现方法。

转载地址：http://jfmm.baihongyu.com/