动态规划（Dynamic Programming）概述\n\n动态规划是一种常见的问题求解方法，通过将问题拆分成多个子问题，并记录已经解决的子问题的解，来降低问题的复杂度。它通常适用于具有最优子结构和重叠子问题的问题。\n\n本文将介绍动态规划的几种常见应用场景，包括坐标型DP、线性DP、区间DP、背包DP和树型DP，并给出相应的C++代码示例。\n\n## 坐标型DP\n\n坐标型DP通常用于处理二维坐标上的问题，每个位置的状态由其周围位置的状态决定。以下是一个示例问题：在一个m x n的网格中，从左上角到右下角，每次只能向右或向下移动，求解从起点到终点的最短路径和。\n\ncpp\nint minPathSum(vector<vector<int>>& grid) {\n int m = grid.size();\n int n = grid[0].size();\n \n vector<vector<int>> dp(m, vector<int>(n, 0));\n dp[0][0] = grid[0][0];\n \n for (int i = 1; i < m; i++) {\n dp[i][0] = dp[i-1][0] + grid[i][0];\n }\n \n for (int j = 1; j < n; j++) {\n dp[0][j] = dp[0][j-1] + grid[0][j];\n }\n \n for (int i = 1; i < m; i++) {\n for (int j = 1; j < n; j++) {\n dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];\n }\n }\n \n return dp[m-1][n-1];\n}\n\n\n## 线性DP\n\n线性DP通常用于处理一维序列上的问题，每个位置的状态由其前面位置的状态决定。以下是一个示例问题：给定一个数组，求解其最大连续子序列和。\n\ncpp\nint maxSubArray(vector<int>& nums) {\n int n = nums.size();\n \n vector<int> dp(n, 0);\n dp[0] = nums[0];\n \n int maxSum = dp[0];\n \n for (int i = 1; i < n; i++) {\n dp[i] = max(nums[i], dp[i-1] + nums[i]);\n maxSum = max(maxSum, dp[i]);\n }\n \n return maxSum;\n}\n\n\n## 区间DP\n\n区间DP通常用于处理区间上的问题，每个区间的状态由其子区间的状态决定。以下是一个示例问题：给定一个字符串，求解将其分割成回文串的最小切割次数。\n\ncpp\nint minCut(string s) {\n int n = s.length();\n \n vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));\n vector<int> dp(n, 0);\n \n for (int i = 0; i < n; i++) {\n dp[i] = i;\n for (int j = 0; j <= i; j++) {\n if (s[j] == s[i] && (j+1 > i-1 || isPalindrome[j+1][i-1])) {\n isPalindrome[j][i] = true;\n dp[i] = (j == 0) ? 0 : min(dp[i], dp[j-1] + 1);\n }\n }\n }\n \n return dp[n-1];\n}\n\n\n## 背包DP\n\n背包DP通常用于处理背包问题，每个物品的状态由其前面物品的状态决定。以下是一个示例问题：给定一组物品和一个背包容量，求解将物品放入背包的最大价值。\n\ncpp\nint knapsack(vector<int>& weights, vector<int>& values, int capacity) {\n int n = weights.size();\n \n vector<vector<int>> dp(n+1, vector<int>(capacity+1, 0));\n \n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= capacity; j++) {\n if (weights[i-1] <= j) {\n dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);\n } else {\n dp[i][j] = dp[i-1][j];\n }\n }\n }\n \n return dp[n][capacity];\n}\n\n\n## 树型DP\n\n树型DP通常用于处理树上的问题，每个节点的状态由其子节点的状态决定。以下是一个示例问题：给定一棵二叉树，求解其最大路径和。\n\ncpp\nstruct TreeNode {\n int val;\n TreeNode* left;\n TreeNode* right;\n TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n};\n\nint maxPathSum(TreeNode* root) {\n int maxSum = INT_MIN;\n maxPathSumHelper(root, maxSum);\n return maxSum;\n}\n\nint maxPathSumHelper(TreeNode* node, int& maxSum) {\n if (node == NULL) {\n return 0;\n }\n \n int leftSum = max(0, maxPathSumHelper(node->left, maxSum));\n int rightSum = max(0, maxPathSumHelper(node->right, maxSum));\n \n maxSum = max(maxSum, node->val + leftSum + rightSum);\n \n return node->val + max(leftSum, rightSum);\n}\n\n\n以上就是动态规划的几种常见应用场景以及相应的C++代码示例。动态规划是一种非常重要的算法思想，掌握了动态规划的基本原理和常见解题方法，可以帮助我们更好地解决各种复杂的问题。