Rust语言从入门到精通系列 - 动态规划算法实践
动态规划算法是一种常见的优化算法，可以用于解决许多复杂的问题。本教程介绍了动态规划算法的基本概念和原理，并提供了 Rust 语言示例代码。通过学习本教程，你应该能够理解动态规划算法的基本思想，以及如何使用 Rust 语言实现它。
动态规划算法
动态规划算法是一种通过将问题分解为子问题来解决复杂问题的算法。它通常用于优化问题，其中需要找到最优解或最大值。 动态规划算法的核心思想是将问题分解为更小的子问题，并将它们的解存储在一个表格中。然后，通过查找表格中的值来计算原始问题的解。这种方法可以避免重复计算子问题，从而提高效率。 动态规划算法通常用于解决以下类型的问题：
- 最长公共子序列
- 背包问题
- 最短路径问题
- 最大子序列和问题
- 动态规划算法的步骤
动态规划算法通常包括以下步骤：
- 定义子问题：将原始问题分解为子问题。
- 定义状态：确定要存储的信息以解决子问题。
- 定义状态转移方程：确定如何计算子问题的解。
- 计算最终解：将子问题的解组合成原始问题的解。
Rust 语言示例实践
最长公共子序列
以下是一个使用动态规划算法解决最长公共子序列问题的 Rust 语言示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
fn longest_common_subsequence(s1: &str, s2: &str) -> String {
let mut table = vec![vec![0; s2.len() + 1]; s1.len() + 1];
for (i, c1) in s1.chars().enumerate() {
for (j, c2) in s2.chars().enumerate() {
if c1 == c2 {
table[i + 1][j + 1] = table[i][j] + 1;
} else {
table[i + 1][j + 1] = std::cmp::max(table[i + 1][j], table[i][j + 1]);
}
}
}
let mut result = String::new();
let mut i = s1.len();
let mut j = s2.len();
while i > 0 && j > 0 {
if table[i][j] == table[i - 1][j] {
i -= 1;
} else if table[i][j] == table[i][j - 1] {
j -= 1;
} else {
result.push(s1.chars().nth(i - 1).unwrap());
i -= 1;
j -= 1;
}
}
result.chars().rev().collect()
}
fn main() {
let s1 = "ABCD";
let s2 = "ACDF";
let result = longest_common_subsequence(s1, s2);
println!("Longest common subsequence of {} and {} is {}", s1, s2, result);
}
// 输出结果
// Longest common subsequence of ABCD and ACDF is ACD
以上代码使用一个二维表格来存储子问题的解，并使用状态转移方程来计算表格中的值。最后，它将子问题的解组合成原始问题的解。
解决背包问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
fn knapsack(weights: &[u32], values: &[u32], capacity: u32) -> u32 {
let n = weights.len();
let mut table = vec![vec![0; capacity as usize + 1]; n + 1];
for i in 0..=n {
for j in 0..=capacity as usize {
if i == 0 || j == 0 {
table[i][j] = 0;
} else if weights[i - 1] as usize <= j {
table[i][j] = std::cmp::max(values[i - 1] + table[i - 1][j - weights[i - 1] as usize], table[i - 1][j]);
} else {
table[i][j] = table[i - 1][j];
}
}
}
table[n][capacity as usize]
}
fn main() {
let weights = vec![2, 3, 4, 5];
let values = vec![3, 4, 5, 6];
let capacity = 8;
let result = knapsack(&weights, &values, capacity);
println!("Maximum value that can be obtained with a capacity of {} is {}", capacity, result);
}
以上代码使用一个二维表格来存储子问题的解，并使用状态转移方程来计算表格中的值。最后，它返回表格中最后一个元素的值，即原始问题的解。
最长上升子序列
最长上升子序列是一个序列中最长的子序列，使得其中的元素按升序排列。以下是使用动态规划算法解决最长上升子序列问题的 Rust 语言示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
fn longest_increasing_subsequence(nums: &[i32]) -> usize {
let n = nums.len();
let mut dp = vec![1; n];
for i in 1..n {
for j in 0..i {
if nums[i] > nums[j] {
dp[i] = std::cmp::max(dp[i], dp[j] + 1);
}
}
}
*dp.iter().max().unwrap()
}
fn main() {
let nums = vec![10, 9, 2, 5, 3, 7, 101, 18];
let result = longest_increasing_subsequence(&nums);
println!("Length of longest increasing subsequence in {:?} is {}", nums, result);
}
以上代码使用一个一维数组来存储子问题的解，并使用状态转移方程来计算数组中的值。最后，它返回数组中的最大值，即原始问题的解。
最大子序列和
最大子序列和是一个序列中最大的子序列和。以下是使用动态规划算法解决最大子序列和问题的 Rust 语言示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
fn max_subarray(nums: &[i32]) -> i32 {
let mut max_sum = nums[0];
let mut cur_sum = nums[0];
for &num in nums.iter().skip(1) {
cur_sum = std::cmp::max(num, cur_sum + num);
max_sum = std::cmp::max(max_sum, cur_sum);
}
max_sum
}
fn main() {
let nums = vec![-2, 1, -3, 4, -1, 2, 1, -5, 4];
let result = max_subarray(&nums);
println!("Maximum subarray sum of {:?} is {}", nums, result);
}
// 输出结果：
// Maximum subarray sum of [-2, 1, -3, 4, -1, 2, 1, -5, 4] is 6
以上代码使用一个变量来存储子问题的解，并使用状态转移方程来计算变量的值。最后，它返回变量的值，即原始问题的解。
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。欢迎转载、使用、重新发布，但务必保留文章署名 TinyZ Zzh （包含链接： https://tinyzzh.github.io ），不得用于商业目的，基于本文修改后的作品务必以相同的许可发布。 如有任何疑问，请 与我联系 (tinyzzh815@gmail.com) 。
评论