动态规划（Dynamic Programming）概述

动态规划是一种常见的问题求解方法，通过将问题拆分成多个子问题，并记录已经解决的子问题的解，来降低问题的复杂度。它通常适用于具有最优子结构和重叠子问题的问题。

本文将介绍动态规划的几种常见应用场景，包括坐标型DP、线性DP、区间DP、背包DP和树型DP，并给出相应的C++代码示例。

坐标型DP

坐标型DP通常用于处理二维坐标上的问题，每个位置的状态由其周围位置的状态决定。以下是一个示例问题：在一个m x n的网格中，从左上角到右下角，每次只能向右或向下移动，求解从起点到终点的最短路径和。

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = grid[0][0];
    
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    
    return dp[m-1][n-1];
}

线性DP

线性DP通常用于处理一维序列上的问题，每个位置的状态由其前面位置的状态决定。以下是一个示例问题：给定一个数组，求解其最大连续子序列和。

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    
    vector<int> dp(n, 0);
    dp[0] = nums[0];
    
    int maxSum = dp[0];
    
    for (int i = 1; i < n; i++) {
        dp[i] = max(nums[i], dp[i-1] + nums[i]);
        maxSum = max(maxSum, dp[i]);
    }
    
    return maxSum;
}

区间DP

区间DP通常用于处理区间上的问题，每个区间的状态由其子区间的状态决定。以下是一个示例问题：给定一个字符串，求解将其分割成回文串的最小切割次数。

int minCut(string s) {
    int n = s.length();
    
    vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));
    vector<int> dp(n, 0);
    
    for (int i = 0; i < n; i++) {
        dp[i] = i;
        for (int j = 0; j <= i; j++) {
            if (s[j] == s[i] && (j+1 > i-1 || isPalindrome[j+1][i-1])) {
                isPalindrome[j][i] = true;
                dp[i] = (j == 0) ? 0 : min(dp[i], dp[j-1] + 1);
            }
        }
    }
    
    return dp[n-1];
}

背包DP

背包DP通常用于处理背包问题，每个物品的状态由其前面物品的状态决定。以下是一个示例问题：给定一组物品和一个背包容量，求解将物品放入背包的最大价值。

int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    
    vector<vector<int>> dp(n+1, vector<int>(capacity+1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (weights[i-1] <= j) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    
    return dp[n][capacity];
}

树型DP

树型DP通常用于处理树上的问题，每个节点的状态由其子节点的状态决定。以下是一个示例问题：给定一棵二叉树，求解其最大路径和。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int maxPathSum(TreeNode* root) {
    int maxSum = INT_MIN;
    maxPathSumHelper(root, maxSum);
    return maxSum;
}

int maxPathSumHelper(TreeNode* node, int& maxSum) {
    if (node == NULL) {
        return 0;
    }
    
    int leftSum = max(0, maxPathSumHelper(node->left, maxSum));
    int rightSum = max(0, maxPathSumHelper(node->right, maxSum));
    
    maxSum = max(maxSum, node->val + leftSum + rightSum);
    
    return node->val + max(leftSum, rightSum);
}

以上就是动态规划的几种常见应用场景以及相应的C++代码示例。动态规划是一种非常重要的算法思想，掌握了动态规划的基本原理和常见解题方法，可以帮助我们更好地解决各种复杂的问题