Count ways to distribute candies

Dynamic Programming

63.9% acceptance

Mar 31, 2026

No description available.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn ways_to_distribute(n: i32, k: i32) -> i32 {
    let modp: i64 = 1_000_000_007;
    let n = n as usize;
    let k = k as usize;
    // Stirling numbers of the second kind S(n, k)
    // S(n, k) = k * S(n-1, k) + S(n-1, k-1)
    // S(n, 1) = 1, S(n, n) = 1
    let mut dp = vec![vec![0i64; k + 1]; n + 1];
    for i in 1..=n {
      dp[i][1] = 1;
      if i <= k {
        dp[i][i] = 1;
      }
    }
    for i in 3..=n {
      for j in 2..=k.min(i - 1) {
        dp[i][j] = ((j as i64 * dp[i - 1][j]) % modp + dp[i - 1][j - 1]) % modp;
      }
    }
    dp[n][k] as i32
  }
}