Rust语言从入门到精通系列 - 动态规划算法实践

1
fn longest_common_subsequence(s1: &str, s2: &str) -> String {
2
    let mut table = vec![vec![0; s2.len() + 1]; s1.len() + 1];
3
    for (i, c1) in s1.chars().enumerate() {
4
        for (j, c2) in s2.chars().enumerate() {
5
            if c1 == c2 {
6
                table[i + 1][j + 1] = table[i][j] + 1;
7
            } else {
8
                table[i + 1][j + 1] = std::cmp::max(table[i + 1][j], table[i][j + 1]);
9
            }
10
        }
11
    }
12
    let mut result = String::new();
13
    let mut i = s1.len();
14
    let mut j = s2.len();
15
    while i > 0 && j > 0 {
16
        if table[i][j] == table[i - 1][j] {
17
            i -= 1;
18
        } else if table[i][j] == table[i][j - 1] {
19
            j -= 1;
20
        } else {
21
            result.push(s1.chars().nth(i - 1).unwrap());
22
            i -= 1;
23
            j -= 1;
24
        }
25
    }
26
    result.chars().rev().collect()
27
}
28

29
fn main() {
30
    let s1 = "ABCD";
31
    let s2 = "ACDF";
32
    let result = longest_common_subsequence(s1, s2);
33
    println!("Longest common subsequence of {} and {} is {}", s1, s2, result);
34
}
35
//  输出结果
36
//  Longest common subsequence of ABCD and ACDF is ACD

1
fn knapsack(weights: &[u32], values: &[u32], capacity: u32) -> u32 {
2
    let n = weights.len();
3
    let mut table = vec![vec![0; capacity as usize + 1]; n + 1];
4
    for i in 0..=n {
5
        for j in 0..=capacity as usize {
6
            if i == 0 || j == 0 {
7
                table[i][j] = 0;
8
            } else if weights[i - 1] as usize <= j {
9
                table[i][j] = std::cmp::max(values[i - 1] + table[i - 1][j - weights[i - 1] as usize], table[i - 1][j]);
10
            } else {
11
                table[i][j] = table[i - 1][j];
12
            }
13
        }
14
    }
15
    table[n][capacity as usize]
16
}
17

18
fn main() {
19
    let weights = vec![2, 3, 4, 5];
20
    let values = vec![3, 4, 5, 6];
21
    let capacity = 8;
22
    let result = knapsack(&weights, &values, capacity);
23
    println!("Maximum value that can be obtained with a capacity of {} is {}", capacity, result);
24
}

1
fn longest_increasing_subsequence(nums: &[i32]) -> usize {
2
    let n = nums.len();
3
    let mut dp = vec![1; n];
4
    for i in 1..n {
5
        for j in 0..i {
6
            if nums[i] > nums[j] {
7
                dp[i] = std::cmp::max(dp[i], dp[j] + 1);
8
            }
9
        }
10
    }
11
    *dp.iter().max().unwrap()
12
}
13

14
fn main() {
15
    let nums = vec![10, 9, 2, 5, 3, 7, 101, 18];
16
    let result = longest_increasing_subsequence(&nums);
17
    println!("Length of longest increasing subsequence in {:?} is {}", nums, result);
18
}

1
fn max_subarray(nums: &[i32]) -> i32 {
2
    let mut max_sum = nums[0];
3
    let mut cur_sum = nums[0];
4
    for &num in nums.iter().skip(1) {
5
        cur_sum = std::cmp::max(num, cur_sum + num);
6
        max_sum = std::cmp::max(max_sum, cur_sum);
7
    }
8
    max_sum
9
}
10

11
fn main() {
12
    let nums = vec![-2, 1, -3, 4, -1, 2, 1, -5, 4];
13
    let result = max_subarray(&nums);
14
    println!("Maximum subarray sum of {:?} is {}", nums, result);
15
}
16
// 输出结果：
17
// Maximum subarray sum of [-2, 1, -3, 4, -1, 2, 1, -5, 4] is 6