number of partitions of n into at most m parts

gistfile1.txt

// use dp to speed up

def Count(n: Int, m: Int) = {
  def Loop(n: Int, m: Int, max: Int): Int = {
    if (m == 0) {
      if (n == 0) 1 else 0
    } else {
      (0 to Math.min(max, n)).map({ x => Loop(n - x, m - 1, x) }).sum
    }
  }
  Loop(n, m, n)
}

def Count(n: Int, m: Int): Int = {
  if (n < 0)
    0
  else if (n == 0)
    1
  else
    (1 to m).map({ x => Count(n - x, x) }).sum
}

def Count(n: Int, m: Int): Int = {
  if (m == 1)
    1
  else if (n < 0)
    0
  else if (n == 0)
    1
  else
    Count(n, m - 1) + Count(n - m, m)
}