序列DP

1751. 最多可以参加的会议数目 II

这一题是01背包的一个类型的，对于每一个会议来说，无非就是选和不选两种情况

DP[i][j]定义0..=i的会议中，不超过j个会议的（这个是约束）最大收益

  1. 不选的话DP[i][j] = DP[i-1][j]
  2. 选的话，就需要找到上一个可以参加的会议，这也是这一题不同于传统背包的点。我们定义上一个会议为编号为last，那么DP[i][j] = DP[last][j-1] + val[last]

对last的查找，我们首先使用一个排序，按照其中的结束时间进行排序，然后从当前往前遍历，找到上一个结束时间小于（没有等于是因为题目要求）目前开始时间的。
Debug的过程中，找到了为什么是不超过，因为比如我要求返回的值是DP[1][2]即只有一场会议，但是是约束是小于等于两场，因此需要把DP[1][1]正确的传递下去，而这一步在主要的k的遍历中实现了，没有说，k>i-1的时候就停止了。通过last实现了这种传递性。（主要是出现在初始化的时候）

  1. pub fn max_value(mut events: Vec<Vec<i32>>, k: i32) -> i32 {
  2.     // 首先根据结束时间进行排序
  3.     let k = k as usize;
  4.     events.sort_by(|a, b| {a[1].cmp( &b[1])});
  5.     // 定义DP[i][j]为0..=i-1个会议时，在选取会议数量为j时的最大收益
  6.     let mut dp = vec![vec![0; (k+1) as usize]; events.len()+1];
  7.     // 注意，右挪了1，第i考虑的是第i-1场会议
  8.     (1..=events.len()).for_each(|i| {
  9.         let (s, e, v) = (events[i-1][0], events[i-1][1], events[i-1][2]);
  11.         // 查找上一场会议last
  12.         let mut last = 0;
  13.         for j in (1..=i - 1).rev() {
  14.             let e_last = events[j-1][1];
  15.             if e_last < s {
  16.                 last = j;
  17.                 break;
  18.             }
  19.         }
  21.         // dp主体,k代表的会议必须大于等于1，初始化也没啥问题
  22.         for j in 1..=k {
  23.             dp[i][j] = dp[i-1][j].max(dp[last][j-1] + v);
  24.         }
  25.     });
  26.     dp[events.len()][k]
  27. }

二分优化

    pub fn max_value(mut events: Vec<Vec<i32>>, k: i32) -> i32 {
        // 首先根据结束时间进行排序
        let k = k as usize;
        events.sort_by(|a, b| {a[1].cmp( &b[1])});
        // 定义DP[i][j]为0..=i-1个会议时，在选取会议数量为j时的最大收益
        let mut dp = vec![vec![0; (k+1) as usize]; events.len()+1];
        // 注意，右挪了1，第i考虑的是第i-1场会议
        (1..=events.len()).for_each(|i| {
            let (s, e, v) = (events[i-1][0], events[i-1][1], events[i-1][2]);

            // 二分查找,右二分
            let (mut l, mut r) = (1, i-1);
            while l < r {
                let mid = (l + r + 1)>>1;
                // 注意这里是mid-1
                if events[mid-1][1] < s { l = mid; }
                else { r = mid-1; }
            }
            let last = if r > 0 && events[r-1][1] < s { r } else { 0 };

            // dp主体,k代表的会议必须大于等于1，初始化也没啥问题
            for j in 1..=k {
                dp[i][j] = dp[i-1][j].max(dp[last][j-1] + v);
            }
        });
        dp[events.len()][k]
    }