Dynamic Programming Solution (Rust)
We can turn the question into "How many buckets can we detect with N pigs in M round"\nWe can mark it as Q(N, M)\nAnd we can prove that Q(N, M) = C(N, N) * Q(0,
We can turn the question into "How many buckets can we detect with N pigs in M round"\nWe can mark it as Q(N, M)\nAnd we can prove that Q(N, M) = C(N, N) * Q(0, M - 1) + C(N, N - 1) * Q(1, M - 1) + ... + C(N, 0) * Q(N, M - 1):  # C(X, Y) is the binomial coefficients.\nEach item C(N, N - X) * Q(X, M - 1) on the right side of the equation is corresponding to groups of buckets each needs X pigs in M - 1 round to figure out the poisonous one if it has the poisonous buckets. And we will mix the group and give them to N - X pigs, there are C(N, N - X) such groups, so the total buckets covered will be C(N, N - X) * Q(X, M - 1).\n\nFor example, let\'s start with 3 pigs and 2 rounds. \nIf a single pig dies in the first round, we can find the corresponding group consist of Q(2, 1) = 4 buckets. \nIf two pigs dies, the corresponding group will have the size of Q(1, 1) = 2 buckets, we can found it on the next round by feed them to 2 pigs using a binary encoding.\nIf no pig dies, the corresponding group will have the size of Q(3, 1) = 8 buckets \nIf all pig dies, the corresponding group will have the size of Q(0, 1) = 1 buckets which means we have found the poisonous one.\nOn each round, some pigs will die, but the rest of pigs can handle the size of the group encoded by dying pigs.\nSo the total buckets we can handle with 3 pigs in 2 rounds is 27 buckets:\n\n![image](https://assets.leetcode.com/users/images/b8973244-6a69-4612-bc55-410ef7efd3c4_1659799082.0977452.png)\n\n\nSo we can program as below:\n```\nuse std::collections::HashMap;\n\nimpl Solution {\n  pub fn poor_pigs(buckets: i32, minutes_to_die: i32, minutes_to_test: i32) -> i32 {\n    if buckets == 1 {\n      return 0\n    }\n\n    let count = minutes_to_test / minutes_to_die;\n    let mut dp = HashMap::<(i32, i32), i32>::new();\n    let mut combo = HashMap::<(i32, i32), i32>::new();\n\n    let mut pigs = 1;\n    loop {\n      let max_buckets = Self::helper(&mut dp, &mut combo, pigs, count);\n      if max_buckets >= buckets {\n        return pigs\n      }\n      pigs += 1;\n    }\n  }\n\n  fn helper(dp: &mut HashMap<(i32, i32), i32>, combo: &mut HashMap<(i32, i32), i32>, pigs: i32, count: i32) -> i32 {\n    if pigs == 0 {\n      return 1\n    } \n\n    let key = (pigs, count);\n    if dp.contains_key(&key) {\n      return *dp.get(&key).unwrap()\n    }\n\n    let result = if count == 1 {\n      2i32.pow(pigs as u32)\n    } else {\n      let mut sum = 0;\n      for i in 0..=pigs {\n        let x = Self::combo(combo, pigs, i) * Self::helper(dp, combo, i, count - 1);\n        sum += x;\n      }\n      sum\n    };\n    dp.insert(key, result);\n    result\n  }\n\n  fn combo(combo: &mut HashMap<(i32, i32), i32>, n: i32, k: i32) -> i32 {\n    if k == 0 {\n      return 1\n    } else if k == 1 {\n      return n\n    } else if k == n {\n      return 1\n    }\n\n    let key = (n, k);\n    if combo.contains_key(&key) {\n      *combo.get(&key).unwrap()\n    } else {\n      let result = Self::combo(combo, n - 1, k - 1) + Self::combo(combo, n - 1, k);\n      combo.insert(key, result);\n      result\n    }\n  }\n}\n```
[]