浅谈动态规划

持续更新中

1 什么是动态规划

动态规划既是一种数学优化方法，也是一种算法范式。该方法由理查德·贝尔曼 (Richard Bellman) 在 20 世纪 50 年代开发，已在从航空航天工程到经济学等众多领域得到应用。为了适用动态规划，问题必须具有两个关键属性：最优子结构和重叠子问题。如果一个问题可以通过组合非重叠子问题的最优解来解决，则该策略称为“分治”，这就是为什么归并排序和快速排序不属于动态规划问题的原因。最优子结构是指给定优化问题的解可以通过其子问题的最优解的组合来获得。这种最优子结构通常通过递归的方式来描述¹。

从一个简单的例子介绍，那就是斐波那契数列（Fibonacci Sequence），它可以通过递推的方法定义：可以发现，这个递推公式就是一个递归定义，因此我们可以通过程序实现求解：

fn fib(n: i32) -> i32 {
    if n == 0 {
        return 0;
    } else if n == 1 {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

前面提到，动态规划问题的关键属性是重叠子问题。重叠子问题指的是，子问题的空间必须很小，即任何解决该问题的递归算法都应该一遍又一遍地解决相同的子问题，而不是产生新的子问题。显然，以上面的斐波那契数列的递归算法为例，如果要计算fib(5)，则计算过程：

每个节点都是一次计算，注意到整个过程中计算了两次fib(3)，计算了三次fib(2)。当继续增大时，可以明显地看出计算过程存在大量重复计算（可以证明其时间复杂度是指数级），这就是重叠子问题。

所谓动态规划，就是考虑了在原有递归算法中重叠子问题的情况，让整个算法只解决每个子问题一次，因此解释了开头提到的：动态规划算法是一种数学优化方法。

使用动态规划可以大大提高其性能，具体来说有两种方式，自上而下和自下而上。

1.1 自上而下的方法

很自然的一个想法是，当第一次计算fib(k)时，我们将计算结果保存下来，当后面需要再次计算fib(k)时，就从保存的结果中直接拿来用。

fn fib(n: i32) -> i128 {
    let mut mem = vec![-1; n as usize + 1];
    fn fib_(n: i32, mut mem: &mut Vec<i128>) -> i128 {
        if n == 0 {
            return 0;
        } else if n == 1 {
            return 1;
        } else if mem[n as usize] == -1 {
            mem[n as usize] = fib_(n - 1, &mut mem) + fib_(n - 2, &mut mem);
        }
        return mem[n as usize];
    }

    return fib_(n, &mut mem);
}

这里通过定义一个mem来实现保存计算结果的功能，其中mem[i]表示fib(i)的结果，每当我们尝试解决一个新的子问题时，首先检查这个vector以查看它是否已经计算过了。如果已经记录了结果，我们可以直接使用它，否则我们需要计算并将其结果记录到vector中。

经过优化过的算法只需要的时间复杂度，不过空间复杂度变为。

1.2 自下而上的方法

一旦我们按照子问题递归地制定问题的解决方案，我们就可以尝试以自下而上的方式重新制定问题。通过使用小子问题的解决方案迭代地生成越来越大的子问题的解决方案。例如，我们已知fib(40)和fib(41)的值，就可以直接计算fib(42)的值。

fn fib(n: i32) -> i128 {
    let mut mem = vec![-1; n as usize + 1];
    mem[0] = 0;
    mem[1] = 1;

    for i in 2..=n {
        mem[i as usize] = mem[(i - 1) as usize] + mem[(i - 2) as usize];
    }

    return mem[n as usize];
}

我们从小到大构建mem数组，最终返回mem[n]就是所需的fib(n)。这种方式仍需要的时间复杂度，的空间复杂度。

当然，还可以继续优化这个过程，由于我们从小到大计算结果，因此不需要存储个元素的计算结果：

fn fib(n: i32) -> i128 {
    if n == 0 {
        return 0;
    } else {
        let mut previous: i128 = 0;
        let mut current = 1;
        for _ in 0..n - 1 {
            let new_fib = previous + current;
            previous = current;
            current = new_fib;
        }
        return current;
    }
}

在这个例子中，我们只需要维护previous和current即可，时间复杂度为，空间复杂度为。

使用自下而上的方法另一点好处在于，并不需要递归调用，因此减少了系统栈空间的调用消耗。

2 一些例子

2.1 爬楼梯

以70.爬楼梯为例，分析题目可以看出，这与斐波那契数列很类似，我们要计算第n阶台阶可选择的方式，就相当于计算爬(n-1)+(n-2)阶台阶可选择的方式之和。因此可以写出递推公式：只是初始条件有一些变化，仍然可以用自底向上的方式进行动态规划：

impl Solution {
    pub fn climb_stairs(n: i32) -> i32 {
        if n == 1 {
            return 1;
        } else {
            let mut previous = 1;
            let mut current = 2;
            for i in 2..n {
                let new_num = previous + current;
                previous = current;
                current = new_num;
            }
            return current;
        }
    }
}

2.2 三角形最小路径和

120. 三角形最小路径和同样也是一个递归问题，我们可以通过高度height和当前高度位置pos的二元组来描述树中的每个节点。比如代表树根节点，表示从上往下树中第三行第三个节点的元素。

根据题目要求，每一步只能移动到下一行中相邻的节点上。假设当前处在位置，下一步可能移动到两个节点和，由于题目是三角形，满足triangle[i].length == triangle[i - 1].length + 1，因此无需担心pos加一后溢出的问题。下面要做的就是比较和两个节点元素的大小即可，这是一个递归的过程。

下面给出初始递归代码：

use std::cmp;
struct Solution;

impl Solution {
    fn rec(triangle: &Vec<Vec<i32>>, height: usize, pos: usize) -> i32 {
        if triangle.len() - 1 > height {
            let min_ = cmp::min(
                Solution::rec(&triangle, height + 1, pos),
                Solution::rec(&triangle, height + 1, pos + 1),
            );
            return min_ + triangle[height][pos];
        } else {
            return triangle[height][pos];
        }
    }

    pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
        return Solution::rec(&triangle, 0, 0);
    }
}

判断这个递归是否为动态规划的一个关键方法就是判断是否存在重叠子问题。简单分析可以得到，从第三层开始，树中的节点会被重复计算，比如节点会由节点和到达，这就是重叠子问题。

根据前面优化斐波那契数列和爬楼梯问题的经验，我们可以通过自上而下的方式，将递归结果记忆化，保证每个子问题只解决一次。

动态规划求解：

use std::cmp;

struct Solution;
impl Solution {
    fn rec(
        triangle: &Vec<Vec<i32>>,
        height: usize,
        pos: usize,
        mut mem: &mut Vec<Vec<i32>>,
    ) -> i32 {
        if mem[height][pos] != 100000 {
            return mem[height][pos];
        } else {
            let dis;
            if triangle.len() - 1 > height {
                let min_ = cmp::min(
                    Solution::rec(&triangle, height + 1, pos, &mut mem),
                    Solution::rec(&triangle, height + 1, pos + 1, &mut mem),
                );
                dis = triangle[height][pos] + min_;
            } else {
                dis = triangle[height][pos];
            }

            mem[height][pos] = dis;
            return dis;
        }
    }

    pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
        let mut mem = vec![vec![]; triangle.len()];
        for i in 0..triangle.len() {
            mem[i] = vec![100000; triangle[i].len()];
        }
        return Solution::rec(&triangle, 0, 0, &mut mem);
    }
}

2.3 最小路径和

64. 最小路径和也是一个类似的问题，使用二维数组进行记忆化搜索即可：

use std::cmp::{self, min};
struct Solution;

impl Solution {
    fn recursive(grid: &Vec<Vec<i32>>, k: usize, j: usize, mut mem: &mut Vec<Vec<i32>>) -> i32 {
        if mem[k][j] != -1 {
            return mem[k][j];
        } else {
            let min_dis;
            if k < grid.len() - 1 && j < grid[0].len() - 1 {
                min_dis = cmp::min(
                    Solution::recursive(&grid, k + 1, j, &mut mem),
                    Solution::recursive(&grid, k, j + 1, &mut mem),
                );
            } else if k < grid.len() - 1 {
                min_dis = Solution::recursive(&grid, k + 1, j, &mut mem);
            } else if j < grid[0].len() - 1 {
                min_dis = Solution::recursive(&grid, k, j + 1, &mut mem);
            }else{
                return grid[k][j];
            }
            mem[k][j] = min_dis + grid[k][j];
            return mem[k][j];
        }
    }

    pub fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
        let mut mem = vec![vec![]; grid.len()];
        for i in 0..grid.len() {
            mem[i] = vec![-1; grid[i].len()];
        }
        return Solution::recursive(&grid, 0, 0, &mut mem);
    }
}

3 如何发现重叠子问题

有些题目，可能上手时没有思路，可以先思考暴力解法。

比如，343.整数拆分，对于这道题来说，暴力解法就是一个回溯的过程，即递归遍历每一种拆分的可能性，然后求子划分的最大值。在求解的过程中，显然可以发现重叠子问题，此时再针对递归代码进行记忆化搜索即可：

impl Solution {
    fn recursive(n: i32, mut mem: &mut Vec<i32>) -> i32 {
        if n <= 2 {
            return 1;
        }
        if mem[(n-1) as usize] != 0{
            return mem[(n-1) as usize];
        }
        let mut max = 0;
        for i in 1..n {
            let mut res = Solution::recursive(n - i,&mut mem);
            let mut t = n - i;
            if res > n - i {
                t = res;
            } else {
                t = n - i
            }
            if i * t > max {
                max = i * t;
            }
        }
        mem[(n-1) as usize] = max;
        return max;
    }

    pub fn integer_break(n: i32) -> i32 {
        let mut mem = vec![0; n as usize];
        return Solution::recursive(n, &mut mem);
    }
}

对于上面的代码，我们可以将其改写为递推的形式，也就是将记忆化搜索改写为DP，有了前面的铺垫，这里改写起来就很容易：

use std::cmp;

impl Solution {
    pub fn integer_break(n: i32) -> i32 {
        let mut mem = vec![0; (n+1) as usize];
        mem[1] = 1;
        mem[2] = 1;
        for i in 3..=n{
            for j in 2..=i-1{
                mem[i as usize] = cmp::max(mem[i as usize],cmp::max(j*(i-j),j*mem[(i-j) as usize]));
            }
        }
        return mem[n as usize];
    }
}

本题还有更优的方法，可以通过数学归纳法证明，当时，应该将其拆分为尽可能多的3和2，其中优先为3，2次之。所以可以直接对3取余，余数有三种情况：0，1，2，将整数部分记为：

当余数为0时，最简单，直接返回；

当余数为1时，由于，所以需要拆出一个3，凑成，返回；

当余数为2时，返回；

下面是代码实现：

impl Solution {
 pub fn integer_break(n: i32) -> i32 {
     match n {
         2 => return 1,
         3 => return 2,
         _ => {
             let r = n % 3;
             let exp = (n / 3) as u32;
             match r {
                 0 => return 3_i32.pow(exp),
                 1 => return 4 * 3_i32.pow(exp - 1),
                 2 => return 2 * 3_i32.pow(exp),
                 _ => return -1,
             };
         }
     }
 }
}

时间复杂度为。

作为练习，分别尝试采用记忆化搜索和动态规划的方式完成：62.不同路径、63.不同路径 II。

4 状态和状态转移

在重叠子问题中，我们可以定义状态和状态转移方程。所谓状态，就是定义了一个函数，它具有特定的含义，通常指的是描述问题解空间的参数或变量的取值。这些参数或变量记录了求解问题时需要考虑的关键信息，如问题规模、位置、容量等。通过合理定义和管理状态，我们可以将复杂的问题拆分为更小的子问题，并利用状态之间的转移关系来推导出最优解。状态转移则明确了状态之间的转移关系，即描述了这个函数“如何去做”。

考虑198. 打家劫舍，它明显具有重叠子问题，我们可以定义状态为计划偷取这些范围内的个房子。根据这个状态定义，我们要偷取的金额最大值就是的一系列子问题所能偷取的金额加上当前偷取的这个房子金额之和的最大值。假设偷取第个房子所获取的金额为，可以写出它的状态转移方程：根据状态转移方程，就可以写出记忆化搜索的代码：

use std::cmp;

struct Solution;
impl Solution {
    fn recursive(nums: &Vec<i32>, pos: usize, mut mem: &mut Vec<i32>) -> i32 {
        if pos >= nums.len() {
            return 0;
        }

        if mem[pos] != -1 {
            return mem[pos];
        } else {
            let mut max = 0;
            for i in pos..nums.len() {
                max = cmp::max(nums[i] + Solution::recursive(&nums, i + 2, &mut mem), max);
            }
            mem[pos] = max;
            return max;
        }
    }

    pub fn rob(nums: Vec<i32>) -> i32 {
        let mut mem = vec![-1; nums.len()];
        Solution::recursive(&nums, 0, &mut mem)
    }
}

使用动态规划的代码：

use std::cmp;
impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let size = nums.len();
        if size < 2 {
            let mut max = 0;
            for i in nums{
                max = cmp::max(max, i)
            }
            return max;
        }
        let mut mem = vec![-1; size];

        mem[size - 1] = nums[size - 1];
        // 可根据状态转移方程得出
        for i in (0..=size - 2).rev() {
            for j in i..size {
                mem[i] = cmp::max(mem[i], nums[j] + if j + 2 < size { mem[j + 2] } else { 0 })
            }
        }
        mem[0]
    }
}

作为练习，完成213. 打家劫舍 II，首先定义出状态和状态转移方程，然后根据这个定义使用动态规划求解。

5 复杂问题的分析思路

121. 买卖股票的最佳时机

122. 买卖股票的最佳时机 II

123. 买卖股票的最佳时机 III

188. 买卖股票的最佳时机 IV

309. 买卖股票的最佳时机含冷冻期

6 0-1背包问题

动态规划可以求解的一类典型问题被称为“0-1”背包问题。问题是这样的：有一个背包，设它的容纳量为，有编号为的个不同的物品，其中第件物品所占背包的容量为，它的价值为。求如何向背包中放入这些物品，使得不超过容纳量的前提下，放入的物品总价值最大？

可以这样给出状态的定义：表示为考虑将个物品放入容纳量为的背包，使得放入的物品价值最大。

当我们遇到第个物品时，我们可以有两种选择，第一种是忽略掉这个物品，因为有些时候不放入这个物品是最优解；第二种是考虑将这个物品放入背包，首先需要检查当前的背包容量能否放得下这件物品，即检查物品所占的容量是否小于当前的背包容量，如果还有空间，则将其放入背包，此时背包的总价值变为考虑将前面的个物品放入容量为的背包中的最大价值加上。所求的就是第一种方法和第二种方法中所得到的总价值的最大者。因此，给出递推关系，也就是状态转移方程如下：

6.1 递归算法

有了状态转移方程，很容易地就可以写出自顶向下的递归代码：

struct Solution;
use std::cmp;
impl Solution {
    fn get_max_value(w: &Vec<i32>, v: &Vec<i32>, capacity: i32, k: i32) -> i32 {
        // 考虑将 [0..k] 个物品放入容量为 capacity 大小的背包中所获取价值的最大值
        if capacity <= 0 || k < 0 {
            // 容量为空/物品为负，比如考虑 k=-1 的区间 [0..-1] 显然没有物品，此时获取价值为 0
            return 0;
        }

        // 情况1：忽略当前的第 k 件物品，获取 [0..k-1] 容量为 capacity 的背包所能获取价值的最大值
        let mut max_value = Solution::get_max_value(&w, &v, capacity, k - 1);
        if capacity >= w[k as usize] {
            // 只有当前容量大于第 k 件物品所占的容量时，才可以考虑第二种方式
            // 情况2：将当前第 k 件物品放入背包中
            max_value = cmp::max(
                max_value,
                v[k as usize] + Solution::get_max_value(&w, &v, capacity - w[k as usize], k - 1),
            );
        }
        max_value
    }

    fn knapsack01(w: Vec<i32>, v: Vec<i32>, capacity: i32) -> i32 {
        if w.len() == 0 {
            return 0;
        }
        Solution::get_max_value(&w, &v, capacity, (w.len() - 1) as i32)
    }
}

fn main() {
    let weight = vec![1, 2, 3];
    let values = vec![6, 10, 12];
    let result = Solution::knapsack01(weight, values, 5);
    println!("{}", result);
}

6.2 记忆化搜索

分析上一节中的递归代码实现，可以发现具有重叠子问题，它出现在每一次调用get_max_value时，参数capacity和k会出现重复。这里采用记忆化搜索的方式优化：

struct Solution;
use std::cmp;

impl Solution {
    fn get_max_value(w: &Vec<i32>, v: &Vec<i32>, capacity: i32, k: i32,mut mem:&mut Vec<Vec<i32>>) -> i32 {
        // 考虑将 [0..k] 个物品放入容量为 capacity 大小的背包中所获取价值的最大值
        if capacity <= 0 || k < 0 {
            // 容量为空/物品为负，比如考虑 k=-1 的区间 [0..-1] 显然没有物品，此时获取价值为 0
            return 0;
        }
        // 记忆化搜索，首先检查mem
        if mem[k as usize][capacity as usize] != -1{
            return mem[k as usize][capacity as usize];
        }

        // 情况1：忽略当前的第 k 件物品，获取 [0..k-1] 容量为 capacity 的背包所能获取价值的最大值
        let mut max_value = Solution::get_max_value(&w, &v, capacity, k - 1,&mut mem);
        if capacity >= w[k as usize] {
            // 只有当前容量大于第 k 件物品所占的容量时，才可以考虑第二种方式
            // 情况2：将当前第 k 件物品放入背包中
            max_value = cmp::max(
                max_value,
                v[k as usize] + Solution::get_max_value(&w, &v, capacity - w[k as usize], k - 1, &mut mem),
            );
        }
        // 更新mem
        mem[k as usize][capacity as usize] = max_value;
        max_value
    }

    fn knapsack01(w: Vec<i32>, v: Vec<i32>, capacity: i32) -> i32 {
        if w.len() == 0 {
            return 0;
        }
        // mem[i][j]：将 [0..i] 个物品放入容量为 j 大小的背包中所获取价值的最大值
        let mut mem = vec![vec![-1;(capacity+1) as usize];w.len()];
        Solution::get_max_value(&w, &v, capacity, (w.len() - 1) as i32,&mut mem)
    }
}

fn main() {
    let weight = vec![1, 2, 3];
    let values = vec![6, 10, 12];
    let result = Solution::knapsack01(weight, values, 5);
    println!("{}", result);
}

这里的记忆化空间是二维数组mem，其中mem[i][j]表示为将个物品放入容量为大小的背包中所获取价值的最大值。

6.2 动态规划

下面将代码改写为自底向上的方式，也就是动态规划。我们同样需要一个二维数组mem，mem[i][j]表示为将个物品放入容量为大小的背包中所获取价值的最大值。

struct Solution;
use std::cmp;

impl Solution {
    fn knapsack01(w: Vec<i32>, v: Vec<i32>, capacity: i32) -> i32 {
        if w.len() == 0 {
            return 0;
        }
        // mem[i][j]：将 [0..i] 个物品放入容量为 j 大小的背包中所获取价值的最大值
        let mut mem = vec![vec![-1; (capacity + 1) as usize]; w.len()];

        // DP
        // 初始化第一行，就是考虑将第一个物品放入背包的情况
        for j in 0..=capacity {
            mem[0][j as usize] = if w[0] <= j { v[0] } else { 0 };
        }

        for i in 1..w.len() {
            for j in 0..=capacity {
                mem[i][j as usize] = mem[i - 1][j as usize];
                if w[i] <= j {
                    mem[i][j as usize] =
                        cmp::max(mem[i][j as usize], v[i] + mem[i - 1][(j - w[i]) as usize])
                }
            }
        }

        mem[w.len() - 1][capacity as usize]
    }
}
fn main() {
    let weight = vec![1, 2, 3];
    let values = vec![4, 8, 10];
    let result = Solution::knapsack01(weight, values, 5);
    println!("{}", result);
}

通过一个具体例子来说明该算法，假设背包容量为，有三个物品，所占容量分别为，价值分别为。依据该算法，我们需要开辟一个大小的矩阵mem，第行代表考虑将个物品放入背包，第列表示为背包的容量，mem[i][j]的值代表将个物品放入容量为的背包中所能获取的最大价值。如下：

	0	1	2	3	4	5
0
1
2

首先考虑第一行，此时只需要考虑，也就是第一个物品放入背包的情况。

	0	1	2	3	4	5
0	0	4	4	4	4	4
1
2

下面填写第二行，显然mem[1][0]=0。

由于背包容量不足以放下第二件物品，所以mem[1][1]的值应该等于不考虑第二件物品所能获取的最大值，即mem[1][1]=mem[0][1]。

对于mem[1][2]，它可以有两种选择，一种是仍然使用mem[0][2]，另一种是将第二件物品放入，此时获得的收益为：加上“考虑将第一件物品放入容量为所能获取的最大价值”。mem[1][2]=max(mem[0][2],v(1)+mem[0][0])=max(4,8+0)=8。

同理可得该行剩余列的值。

	0	1	2	3	4	5
0	0	4	4	4	4	4
1	0	4	8	12	12	12
2

下面填写第三行，显然mem[2][0]=0,mem[2][1]=4,mem[2][2]=8。

对于mem[2][3]，它可以有两种选择，一种是仍然使用mem[1][3]，另一种是将第三件物品放入，此时获得的收益为：加上“考虑将第二件物品放入容量为所能获取的最大价值”。mem[2][3]=max(mem[1][3],v(2)+mem[1][0])=max(12,10+0)=12。

对于mem[2][4]，它可以有两种选择，一种是仍然使用mem[1][4]，另一种是将第三件物品放入，此时获得的收益为：加上“考虑将第二件物品放入容量为所能获取的最大价值”。mem[2][4]=max(mem[1][4],v(2)+mem[1][1])=max(12,10+4)=14。

对于mem[2][4]，它可以有两种选择，一种是仍然使用mem[1][5]，另一种是将第三件物品放入，此时获得的收益为：加上“考虑将第二件物品放入容量为所能获取的最大价值”。mem[2][4]=max(mem[1][5],v(2)+mem[1][2])=max(12,10+8)=18。

	0	1	2	3	4	5
0	0	4	4	4	4	4
1	0	4	8	12	12	12
2	0	4	8	12	14	18

6.3 优化空间复杂度

对于0-1背包问题，时间复杂度为级别，空间复杂度为级别。对于时间复杂度可以优化的空间很小，但空间复杂度还可以做进一步优化，这是由于我们目前所使用的空间不仅取决于，还取决于的大小。

通过上一节的例子可以发现，当我们更新mem中的第行时，需要使用的仅仅是mem第行的元素，换句话说，此时对于小于行的元素已经不关心了，因此，一个很自然的想法就是能否仅使用两行完成整个算法。

当时，我们初始化mem第一行，当时，更新mem第二行。接下来，当时，我们需要覆盖更新mem第一行，当时，覆盖更新mem第二行……以此类推。

不难发现，当为奇数时，我们需要更新mem[1]，为偶数时，我们需要更新mem[0]，因此可以将代码优化如下：

struct Solution;
use std::cmp;

impl Solution {
    fn knapsack01(w: Vec<i32>, v: Vec<i32>, capacity: i32) -> i32 {
        if w.len() == 0 {
            return 0;
        }
        // mem[i][j]：将 [0..i] 个物品放入容量为 j 大小的背包中所获取价值的最大值
        let mut mem = vec![vec![-1; (capacity + 1) as usize]; 2];

        // DP
        // 初始化第一行，就是考虑将第一个物品放入背包的情况
        for j in 0..=capacity {
            mem[0][j as usize] = if w[0] <= j { v[0] } else { 0 };
        }

        for i in 1..w.len() {
            for j in 0..=capacity {
                mem[i % 2][j as usize] = mem[(i - 1) % 2][j as usize];
                if w[i] <= j {
                    mem[i % 2][j as usize] = cmp::max(
                        mem[i % 2][j as usize],
                        v[i] + mem[(i - 1) % 2][(j - w[i]) as usize],
                    )
                }
            }
        }

        mem[(w.len() - 1) % 2][capacity as usize]
    }
}
fn main() {
    let weight = vec![1, 2, 3];
    let values = vec![4, 8, 10];
    let result = Solution::knapsack01(weight, values, 5);
    println!("{}", result);
}

此时空间复杂度降为级别，我们将空间优化到与无关。

更进一步地，能否将空间再次优化呢，换句话说，我们能否仅使用一行空间来完成整个算法？

重新分析整个算法的步骤，考虑如下情况：

	0	1	2	3	4	5
0	0	4	4	4	4	4
1

此时算法已经进行完第一行，正准备填写下一行。

• 对于mem[1][5]，我们可以根据mem[0][5]和mem[0][2]来填写；
• 对于mem[1][4]，我们可以根据mem[0][4]和mem[0][1]来填写；
• 对于mem[1][3]，我们可以根据mem[0][3]和mem[0][0]来填写；
• 对于mem[1][2]，我们可以根据mem[0][2]来填写（背包容量装不下第三件物品）；
• 对于mem[1][1]，我们可以根据mem[0][1]来填写（背包容量装不下第三件物品）；
• 对于mem[1][0]，我们可以根据mem[0][0]来填写（背包容量装不下第三件物品）；

不难发现，对于mem[i][j]的值，我们只需要mem[i-1][j]和mem[i-1][j-w(i)]，也就是矩阵对应元素上面和左面的元素，对于右面的元素我们并不关心，因此，进一步优化的方式就是：可以使用一行mem，当我们每次更新下一个物品时，将mem从后向前去更新。

这样做还有一个好处，就是当背包容量装不下当前物品时，就可以提前返回了，这对于算法的时间上也进行了提升（常数级别的提升）。

struct Solution;
use std::cmp;

impl Solution {
    fn knapsack01(w: Vec<i32>, v: Vec<i32>, capacity: i32) -> i32 {
        if w.len() == 0 {
            return 0;
        }
        // mem[j]：将物品放入容量为 j 大小的背包中所获取价值的最大值
        let mut mem = vec![-1; (capacity + 1) as usize];

        // DP
        // 考虑将第一个物品放入背包的情况，初始化
        for j in 0..=capacity {
            mem[j as usize] = if w[0] <= j { v[0] } else { 0 };
        }

        for i in 1..w.len() {
            for j in (0..=capacity).rev() {
                if w[i] <= j {
                    mem[j as usize] = cmp::max(mem[j as usize], v[i] + mem[(j - w[i]) as usize])
                }
            }
        }

        mem[capacity as usize]
    }
}
fn main() {
    let weight = vec![1, 2, 3];
    let values = vec![4, 8, 10];
    let result = Solution::knapsack01(weight, values, 5);
    println!("{}", result);
}

经过优化，此时的算法空间复杂度降为级别。

这种将空间优化为一行或两行的技巧称为滚动数组或压缩状态方法，这种方式充分利用了那些失去作用的状态的空间，将它们替换为新的状态。

6.4 变种问题

416. 分割等和子集可以转换为0-1背包问题。这是因为我们可以将问题看做在个数组中选择数字，填满大小的背包。注意，这里需要“填满”。并且注意到，如果数组和为奇数，则一定不可以分割，因此需要先求和判断奇偶。

可以这样定义状态：表示为考虑将个物品填满容纳量为的背包，这里的状态是布尔类型。状态转移方程如下：即对于物品，我们可以有两种选择，第一种是忽略掉它，考虑个物品能否填满容量为的背包，第二种是将其放入背包，此时考察个物品能否填满容量为大小的背包。只要有一种情况满足，则对于当前的物品则可以满足要求。

参考上一节的优化空间复杂度的算法，这里直接给出动态规划解法如下：

impl Solution {
    pub fn can_partition(nums: Vec<i32>) -> bool {
        if nums.len() < 2 {
            return false;
        };
        let sum: i32 = nums.iter().sum();
        if sum & 1 == 0 {
            // even number
            let mut dp = vec![false; (sum >> 1) as usize + 1];
            for i in 0..=(sum >> 1) as usize {
                dp[i] = nums[0] == i as i32;
            }
            for i in 1..nums.len() {
                for j in (0..=(sum >> 1) as usize).rev() {
                    if j as i32 >= nums[i] {
                        dp[j] = dp[j] || (dp[j - nums[i] as usize]);
                    }
                }
            }
            return dp[(sum >> 1) as usize];
        }
        false
    }
}

作为练习，完成698. 划分为k个相等的子集，322. 零钱兑换 、377. 组合总和 Ⅳ、474. 一和零、139. 单词拆分、140. 单词拆分 II、494. 目标和。

7 最长子序列

另外一类可以由动态规划求解的问题，是最长子序列问题（Longest Increasing Subsequence,LIS），见300. 最长递增子序列。这里需要关注题目的描述，我们要寻求的是最长严格递增的子序列，其中子序列是原数组的子集，但不改变在原数组中的顺序。

对于数组中的每一个数字，我们都可以进行两种选择：不选择这个数字加入当前的子序列、选择这个数字加入当前的子序列。但是选择的数字在子序列中的位置不固定，我们无法方便地考察这个问题，因此可以将状态定义如下：表示以第个数字为结尾的最长递增子序列的长度。接下来考虑这样一种情况，当遍历到第个数字时，如果数字大于之前的某个数字，则此时以第个数字结尾的长度等于。这就是最长递增子序列的状态转移方程：可以根据该方程，写出代码具体解：

struct Solution;
use std::cmp;
impl Solution {
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        let mut res = 1;
        let mut dp = vec![1;nums.len()];
        for i in 1..nums.len() {
            for j in 0..i{
                if nums[j] < nums[i] {
                    dp[i] = cmp::max(dp[j] + 1, dp[i]);
                    res = cmp::max(res, dp[i]);
                }
            }
        }
        res
    }
}

fn main() {
    let nums = vec![10,9,2,5,3,7,101,18];
    let result = Solution::length_of_lis(nums);
    println!("{:?}", result);
}

时间复杂度为级别，空间复杂度为级别。

算法还可以继续优化，注意到我们总是关注最长递增子序列的最后一个元素，当每次遍历时，如果可以让已经得到的最长递增子序列的结尾的数越小，则在后续的递推中可以更容易地构成一个新的上升子序列。基于这个思想，我们在每次遍历时，维护更新当前找到的子序列结尾最小元素的值，这样定义的新状态表示为当前长度为的所有上升子序列结尾元素最小的值。在算法实现上，可以使用这样的数组arr来存储状态，并且可以证明，这个状态数组时严格递增的数组，且数组的长度就是最长上升子序列的长度。

因此，我们只需要遍历原序列，对于一个新数字，如果它大于数组arr中的最后一个元素，则将其添加到arr的结尾；否则，查找arr中第一个大于该数字的值，将其更新为当前数字，这样就维护了长度为的所有上升子序列结尾元素最小的值的定义。

另外注意到这里的查找是在一个严格递增的数组上进行，因此可以使用二分查找法。下面是算法实现：

impl Solution {
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        let mut res = 1;
        let mut arr = Vec::new();
        // init arr
        arr.push(nums[0]);
        for i in 1..nums.len() {
            if nums[i] > *arr.last().unwrap(){
                arr.push(nums[i]);
            }else{
                let mut left = 0;
                let mut right = arr.len()-1;
                while left < right {
                    let mid = (left + right) >> 1;
                    if arr[mid] < nums[i] {
                        left = mid + 1;
                    }else{
                        right = mid;
                    }
                }
                // update arr
                arr[left] = nums[i];
            }
        }
        arr.len() as i32
    }
}

经过这样优化后，时间复杂度降低为级别，空间复杂度为级别。

---

1. https://en.wikipedia.org/wiki/Dynamic_programming↩︎