适用场景

  • 问题可以拆成若干 子问题
  • 当前状态的答案可以由 更小规模的状态 推出来
  • 子问题会被 重复计算
  • 题目要求 最值、方案数、是否可行，通常都可能是动态规划

核心思路

  • 先定义 dp[i] 或 dp[i][j] 的含义
  • 找出状态之间的 转移方程
  • 明确 初始状态
  • 按照正确顺序填表或记忆化搜索，最终得到答案

Rust 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fn dp_template(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut dp = vec![0i32; n];

    dp[0] = nums[0];

    for i in 1..n {
        // 1. 状态转移
        dp[i] = dp[i - 1].max(nums[i]);
    }

    // 2. 返回答案
    dp[n - 1]
}

爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fn climb_stairs(n: i32) -> i32 {
    let n = n as usize;
    if n <= 2 {
        return n as i32;
    }

    let mut dp = vec![0i32; n + 1];
    dp[1] = 1;
    dp[2] = 2;

    for i in 3..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    dp[n]
}

代表题

  • 5. 最长回文子串
    题意：给定一个字符串，找出其中最长的回文子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pub fn longest_palindrome(s: String) -> String {
    let bytes = s.as_bytes();
    let n = bytes.len();
    let mut dp = vec![vec![false; n]; n];
    let mut start = 0usize;
    let mut max_len = 1usize;

    for i in (0..n).rev() {
        for j in i..n {
            if bytes[i] == bytes[j] && (j - i <= 2 || dp[i + 1][j - 1]) {
                dp[i][j] = true;
                if j - i + 1 > max_len {
                    start = i;
                    max_len = j - i + 1;
                }
            }
        }
    }

    s[start..start + max_len].to_string()
}
  • 32. 最长有效括号
    题意：给定一个只包含左右括号的字符串，求最长合法括号子串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pub fn longest_valid_parentheses(s: String) -> i32 {
    let bytes = s.as_bytes();
    let n = bytes.len();
    let mut dp = vec![0usize; n];
    let mut ans = 0usize;

    for i in 1..n {
        if bytes[i] == b')' {
            if bytes[i - 1] == b'(' {
                dp[i] = if i >= 2 { dp[i - 2] } else { 0 } + 2;
            } else if dp[i - 1] < i && bytes[i - dp[i - 1] - 1] == b'(' {
                dp[i] = dp[i - 1] + 2;
                if i >= dp[i - 1] + 2 {
                    dp[i] += dp[i - dp[i - 1] - 2];
                }
            }
            ans = ans.max(dp[i]);
        }
    }

    ans as i32
}
  • 62. 不同路径
    题意：机器人从左上角走到右下角，每次只能向右或向下，求不同路径总数。
1
2
3
4
5
6
7
8
9
10
11
12
13
pub fn unique_paths(m: i32, n: i32) -> i32 {
    let m = m as usize;
    let n = n as usize;
    let mut dp = vec![vec![1i32; n]; m];

    for i in 1..m {
        for j in 1..n {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    dp[m - 1][n - 1]
}
  • 64. 最小路径和
    题意：给定一个非负整数网格，从左上角走到右下角，每次只能向右或向下，求路径数字总和的最小值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pub fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut dp = vec![vec![0i32; n]; m];

    dp[0][0] = grid[0][0];

    for i in 1..m {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for j in 1..n {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    for i in 1..m {
        for j in 1..n {
            dp[i][j] = dp[i - 1][j].min(dp[i][j - 1]) + grid[i][j];
        }
    }

    dp[m - 1][n - 1]
}
  • 70. 爬楼梯
    题意：每次可以爬 1 或 2 阶楼梯，给定楼梯总阶数 n，求有多少种不同爬法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pub fn climb_stairs(n: i32) -> i32 {
    let n = n as usize;
    if n <= 2 {
        return n as i32;
    }

    let mut dp = vec![0i32; n + 1];
    dp[1] = 1;
    dp[2] = 2;

    for i in 3..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    dp[n]
}
  • 72. 编辑距离
    题意：给定两个单词，求将一个单词转换成另一个单词所需的最少操作数，操作包括插入、删除、替换。
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
pub fn min_distance(word1: String, word2: String) -> i32 {
    let s1 = word1.as_bytes();
    let s2 = word2.as_bytes();
    let m = s1.len();
    let n = s2.len();
    let mut dp = vec![vec![0i32; n + 1]; m + 1];

    for i in 0..=m {
        dp[i][0] = i as i32;
    }
    for j in 0..=n {
        dp[0][j] = j as i32;
    }

    for i in 1..=m {
        for j in 1..=n {
            if s1[i - 1] == s2[j - 1] {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + dp[i - 1][j - 1].min(dp[i - 1][j].min(dp[i][j - 1]));
            }
        }
    }

    dp[m][n]
}
  • 118. 杨辉三角
    题意：给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {
    let num_rows = num_rows as usize;
    let mut ans = Vec::with_capacity(num_rows);

    for i in 0..num_rows {
        let mut row = vec![1; i + 1];
        for j in 1..i {
            row[j] = ans[i - 1][j - 1] + ans[i - 1][j];
        }
        ans.push(row);
    }

    ans
}
  • 139. 单词拆分
    题意：给定一个字符串和一个字典，判断该字符串能否被拆分成若干个字典中的单词。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
use std::collections::HashSet;

pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
    let n = s.len();
    let words: HashSet<String> = word_dict.into_iter().collect();
    let mut dp = vec![false; n + 1];
    dp[0] = true;

    for i in 1..=n {
        for j in 0..i {
            if dp[j] && words.contains(&s[j..i]) {
                dp[i] = true;
                break;
            }
        }
    }

    dp[n]
}
  • 152. 乘积最大子数组
    题意：给定一个整数数组，求乘积最大的连续子数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
pub fn max_product(nums: Vec<i32>) -> i32 {
    let mut max_dp = nums[0];
    let mut min_dp = nums[0];
    let mut ans = nums[0];

    for &num in nums.iter().skip(1) {
        let candidates = [num, max_dp * num, min_dp * num];
        max_dp = *candidates.iter().max().unwrap();
        min_dp = *candidates.iter().min().unwrap();
        ans = ans.max(max_dp);
    }

    ans
}
  • 198. 打家劫舍
    题意：给定一个数组表示每间房屋的钱数，不能偷相邻的房屋，求能偷到的最大金额。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pub fn rob(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    if n == 1 {
        return nums[0];
    }

    let mut dp = vec![0i32; n];
    dp[0] = nums[0];
    dp[1] = nums[0].max(nums[1]);

    for i in 2..n {
        dp[i] = dp[i - 1].max(dp[i - 2] + nums[i]);
    }

    dp[n - 1]
}
  • 279. 完全平方数
    题意：给定一个整数 n，求和为 n 的完全平方数的最少数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pub fn num_squares(n: i32) -> i32 {
    let n = n as usize;
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;

    for i in 1..=n {
        let mut j = 1usize;
        while j * j <= i {
            dp[i] = dp[i].min(dp[i - j * j] + 1);
            j += 1;
        }
    }

    dp[n]
}
  • 300. 最长递增子序列
    题意：给定一个整数数组，找出其中严格递增子序列的最大长度，子序列不要求连续。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pub fn length_of_lis(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut dp = vec![1i32; n];
    let mut ans = 1i32;

    for i in 0..n {
        for j in 0..i {
            if nums[j] < nums[i] {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
        ans = ans.max(dp[i]);
    }

    ans
}
  • 322. 零钱兑换
    题意：给定若干种硬币面额和目标金额 amount，求凑出该金额所需的最少硬币数；如果无法凑出则返回 -1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
    let amount = amount as usize;
    let mut dp = vec![amount as i32 + 1; amount + 1];
    dp[0] = 0;

    for i in 1..=amount {
        for &coin in &coins {
            let coin = coin as usize;
            if coin <= i {
                dp[i] = dp[i].min(dp[i - coin] + 1);
            }
        }
    }

    if dp[amount] > amount as i32 {
        -1
    } else {
        dp[amount]
    }
}
  • 1143. 最长公共子序列
    题意：给定两个字符串，求它们的最长公共子序列长度，子序列中的字符顺序不能改变，但不要求连续。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
    let s1 = text1.as_bytes();
    let s2 = text2.as_bytes();
    let m = s1.len();
    let n = s2.len();
    let mut dp = vec![vec![0i32; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            if s1[i - 1] == s2[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }

    dp[m][n]
}