C++--动态规划路径问题

**C++ 中的动态规划路径问题**

在计算机科学中，动态规划是一种常见的算法技巧，用于解决复杂的问题。它通过分解问题为更小的子问题，并以递归方式求解这些子问题来实现。这种方法可以显著减少计算量和时间。

本文将讨论 C++ 中的一些动态规划路径问题及其解决方案。

###1. 最长上升子序列（Longest Increasing Subsequence，LIS）

最长上升子序列是指从一组数字中选择出一个子序列，使得该子序列中的每个数字都大于前面的数字。例如，如果我们有序列 {10,22,9,33,21,50,41,60}, 最长上升子序列是 {10,22,33,50,60}。

#### 解决方案

cpp#include <iostream>
#include <vector>

int lis(const std::vector<int>& arr) {
 int n = arr.size();
 if (n ==0)
 return0;

 // dp[i] 表示以 arr[i] 结尾的最长上升子序列长度 std::vector<int> dp(n,1);

 for (int i =1; i < n; ++i) {
 for (int j =0; j < i; ++j) {
 if (arr[i] > arr[j])
 dp[i] = std::max(dp[i], dp[j] +1);
 }
 }

 int maxLis =0;
 for (const auto& val : dp)
 maxLis = std::max(maxLis, val);

 return maxLis;
}

int main() {
 std::vector<int> arr = {10,22,9,33,21,50,41,60};
 int result = lis(arr);
 std::cout << "最长上升子序列长度：" << result << std::endl;
 return0;
}

###2. 最短路径（Shortest Path）

最短路径问题是指在一个图中找到从源点到目标点的最短路径。例如，如果我们有一个图 {A, B, C, D}，其中 A 和 B 相邻，B 和 C 相邻，C 和 D 相邻，我们需要找到从 A 到 D 的最短路径。

#### 解决方案

cpp#include <iostream>
#include <vector>

struct Edge {
 int v;
 int w;
};

bool bellmanFord(const std::vector<Edge>& edges, int n, int src) {
 // dist[i] 表示源点到 i 的距离 std::vector<int> dist(n +1, INT_MAX);
 dist[src] =0;

 for (int i =0; i < n -1; ++i) {
 for (const auto& edge : edges) {
 if (dist[edge.v] != INT_MAX && dist[edge.v] + edge.w < dist[edge.u]) {
 dist[edge.u] = dist[edge.v] + edge.w;
 }
 }
 }

 // 检查是否有负权重环 for (const auto& edge : edges) {
 if (dist[edge.v] != INT_MAX && dist[edge.v] + edge.w < dist[edge.u]) {
 return false; // 有负权重环 }
 }

 return true;
}

int main() {
 int n =4;
 std::vector<Edge> edges = {{0,5}, {1, -3}, {2,7}, {3,6}};
 int src =0;

 bool result = bellmanFord(edges, n, src);
 if (result)
 std::cout << "没有负权重环" << std::endl;
 else std::cout << "有负权重环" << std::endl;

 return0;
}

###3. 最大子矩阵和（Maximum Submatrix Sum）

最大子矩阵和问题是指在一个矩阵中找到一个子矩阵，使得该子矩阵的元素之和最大。例如，如果我们有矩阵 {1,2, -1, -4}, {-5, -3,9,7}, {10,11, -2,8}，我们需要找到一个子矩阵，使得该子矩阵的元素之和最大。

#### 解决方案

cpp#include <iostream>
#include <vector>

int maxSubmatrixSum(const std::vector<std::vector<int>>& matrix) {
 int n = matrix.size();
 if (n ==0)
 return0;

 int m = matrix[0].size();

 // dp[i][j] 表示以 matrix[i][j] 结尾的最大子矩阵和 std::vector<std::vector<int>> dp(n, std::vector<int>(m, INT_MIN));

 for (int i =0; i < n; ++i) {
 for (int j =0; j < m; ++j) {
 if (i ==0 && j ==0)
 dp[i][j] = matrix[i][j];
 else if (i ==0)
 dp[i][j] = std::max(matrix[i][j], dp[i][j -1]);
 else if (j ==0)
 dp[i][j] = std::max(matrix[i][j], dp[i -1][j]);
 else dp[i][j] = std::max(std::max(dp[i -1][j], dp[i][j -1]), matrix[i][j] + dp[i -1][j -1]);
 }
 }

 int maxSum = INT_MIN;
 for (const auto& row : dp)
 for (int val : row)
 maxSum = std::max(maxSum, val);

 return maxSum;
}

int main() {
 std::vector<std::vector<int>> matrix = {{1,2, -1, -4}, {-5, -3,9,7}, {10,11, -2,8}};
 int result = maxSubmatrixSum(matrix);
 std::cout << "最大子矩阵和：" << result << std::endl;
 return0;
}

上述问题都是动态规划路径问题的经典例子。通过使用动态规划技巧，我们可以有效地解决这些问题，得到最优解。

**参考**

* [Wikipedia: Dynamic Programming]( />* [GeeksforGeeks: Dynamic Programming]( />* [LeetCode: Dynamic Programming](