279. 完全平方数

image.png

  1. /// 优化
  2. pub fn num_squares_better(n: i32) -> i32 {
  3.     // 不再需要预处理
  4.     let n = n as usize;
  5.     // 定义dp[i][j]为前i个([0..i])完全平方数和正好为j的最小数量
  6.     let mut dp = vec![0x3f3f3f3f; n + 1];
  7.     // 初始化：用0个物品凑出价值为0的数量为0，直接影响dp[1][0],dp[1][1]
  8.     dp[0] = 0;
  10.     // 一般情况：直接将每个元素都涵盖在这一步去写
  11.     let mut t: usize = 1;
  12.     loop {
  13.         if t*t > n { break; }
  14.         let x = t*t;
  15.         // 确保j比x大
  16.         (x..=n).for_each(|j| {
  17.             dp[j] = dp[j].min(dp[j-x] + 1);
  18.         });
  19.         t += 1;
  20.     }
  22.     dp[n]
  23. }

10. 正则表达式匹配

在会了完全平方式的推导之后，就可以看这一题了，和上一题的共同点在于*可以匹配零个或者多个前面的字符。
题意比较清晰，难点在于将三种情况分析完毕。策略在于，DP的问题都是分析上一个状态如何转移到下一个状态，我们只需要关注转移的三条路径即可。
image.png
这个地方容易有两个迷惑的地方：

  1. 对于*结尾的字符串，上一个状态不是*结尾的，那么这种匹配是否是完备的？显然是完备的，因为虽然上一个状态不是*结尾的，但是我们根据定义的到*结尾情况的上一个状态是j-2不是j-1
  2. 对于*结尾的字符串，我们查找匹配几个应该是往后看i, i+1...还是往前...i-1, i？显然是往前，这是因为dp定义来的，但是会比较反直觉，因此我们每次情况的上一个状态都在变化。

到这里，优化就变成了和上一题一样的思考路径了：
image.png

  1. /// 10. 正则表达式匹配
  2. pub fn is_match(s: String, p: String) -> bool {
  3.     // 技巧：往原字符头部插入空格，这样得到 char 数组是从 1 开始，
  4.     // 而且可以使得 f[0][0] = true，可以将 true 这个结果滚动下去
  5.     let (mut ss, mut pp) = (String::from(" "), String::from(" "));
  6.     ss.extend(s.chars().into_iter());
  7.     pp.extend(p.chars().into_iter());
  9.     let s = ss.chars().collect::<Vec<char>>();
  10.     let p = pp.chars().collect::<Vec<char>>();
  12.     // 定义dp为匹配串中i，模式串中j，两个字符串是否匹配，使用Boolean
  13.     let mut dp = vec![vec![false; pp.len()]; ss.len()];
  14.     dp[0][0] = true;
  16.     // 最有迷惑性的地方，也是符合dp规律的地方就是这两层循环，因为
  17.     // 我们使用到的前序状态是很完备的到p.len()的，因此需要这么写
  18.     for i in 0..s.len() {
  19.         for j in 1..p.len() {
  20.             // 这一步是一个剪枝，可有可无，可以节约时间，但是在实际中这一步有额外的内存开销
  21.             if j+1 < p.len() && p[j+1] == '*' { continue; }
  23.             // 三种情况
  24.             if i >= 1 && p[j] != '*' {
  25.                 dp[i][j] = dp[i-1][j-1] && (p[j] == '.' || p[j] == s[i]);
  26.             }else if p[j] == '*' {
  27.                 dp[i][j] = (j >= 2 && dp[i][j-2]) || (i >= 1 && dp[i-1][j] &&
  28.                     (s[i] == p[j-1] || p[j-1] == '.'));
  29.             }
  30.         }
  31.     }
  32.     dp[s.len()-1][p.len()-1]
  33. }
  35. #[cfg(test)]
  36. mod test{
  37.     use crate::dp::backpack_full::Solution;
  39.     #[test]
  40.     fn test() {
  41.         let res = Solution::is_match(String::from("aaaa"), String::from("a*"));
  42.         assert_eq!(res, true)
  43.     }
  44. }

双层循环以及时间优化，直接debug看看下面的例子就很清晰

638. 大礼包——多维编码

这一题的DFS方法也比较巧，就是假设单买也是礼包，人为的进行类似礼包的编码同时限制礼包的购买数量即可。
不过更关键的是学习这一题是怎么转换为完全背包的以及究竟是如何进行编码的：
image.png
在每一次转换的时候只需要考虑，究竟是单买还是买大礼包即可，思路很简单。完全背包的点在于，每一次需要考虑买几个或者是买几个大礼包。但是注意到了，维度爆炸，这一题真正的难度在于对多维进行编码，先看整体代码，然后一点点看：

impl Solution {
    pub fn shopping_offers(price: Vec<i32>, special: Vec<Vec<i32>>, needs: Vec<i32>) -> i32 {
        let n = price.len();
        let mut g = vec![1; n + 1];
        for i in 1..=n {
            g[i] = g[i-1] * (needs[i-1] + 1);
        }
        println!("g:{:?}", g);

        let mask = g[n];
        let mut f = vec![0; mask as usize];
        let mut cnt = vec![0; n];

        for state in 1..mask as usize {
            f[state] = 0x3f3f3f3f as i32;
            cnt = vec![0; n];
            for i in 0..n {
                cnt[i] = (state as i32) % g[i + 1] / g[i];
            }
            println!("state:{} -->cnt {:?}", state, cnt);
            for i in 0..n {
                if cnt[i] > 0 {
                    f[state] = f[state].min(f[state - g[i] as usize] + price[i]);
                }
            }

            'out: for x in &special {
                let mut cur = state as i32;
                for i in 0..n {
                    if cnt[i] < x[i] { continue 'out; }
                    cur -= x[i] * g[i];
                }
                f[state] = f[state].min(f[cur as usize] + x[n]);
            }
        }

        f[mask as usize - 1]
    }
}

用一个例子，得到一个输出：

[2,3,4]
[[1,1,0,4],[2,2,1,9]]
[1,2,1]

// 输出：
g:[1, 2, 6, 12]
state:1 -->cnt [1, 0, 0]
state:2 -->cnt [0, 1, 0]
state:3 -->cnt [1, 1, 0]
state:4 -->cnt [0, 2, 0]
state:5 -->cnt [1, 2, 0]
state:6 -->cnt [0, 0, 1]
state:7 -->cnt [1, 0, 1]
state:8 -->cnt [0, 1, 1]
state:9 -->cnt [1, 1, 1]
state:10 -->cnt [0, 2, 1]
state:11 -->cnt [1, 2, 1]

就可以一点点的看了，最开始的编码g：

let n = price.len();
let mut g = vec![1; n + 1];
for i in 1..=n {
    g[i] = g[i-1] * (needs[i-1] + 1);
}

得到的是：g:[1, 2, 6, 12]
式子本身的意思是，对于第i个元素，有着needs[i] + 1种可能，即对于我们需要的needs=[1,2,1]中的第一个元素，有两种可能：0,1，在第一个元素选定的基础上，第二个元素有6种可能：0 -[0, 1, 2], 1 - [0, 1, 2]，依次类推。因此总的可能情况为12种，对应12个输出行。
而对于g中存储的元素本身而言，注意，状态1的时候：[1, 0, 0]，状态2的时候：[0, 1, 0]，状态6的时候[0, 0, 1]。这刚好就是单买的情况。
因此对于单买的时候，我们选取上一状态只需要：
注意这里进行了完全背包的压缩，本来是对于第**1/2/3**个物品需要考虑单买情况下，需要买几个的，优化过后就直接是：

for i in 0..n {
    if cnt[i] > 0 {
        f[state] = f[state].min(f[state - g[i] as usize] + price[i]);
    }
}

接下来再考虑需要买几个大礼包，注意这里的解码：

'out: for x in &special {
    // 当前的状态，即几个1几个2几个3
    let mut cur = state as i32;
    for i in 0..n {
        // x[i]代表了大礼包中物品i的数量，因此必须需要的大于大礼包有的
        if cnt[i] < x[i] { continue 'out; }
        // 通过这种方式解码可以得到不同维度的物品需要的量！
        cur -= x[i] * g[i];
    }
    f[state] = f[state].min(f[cur as usize] + x[n]);
}