Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

To be more elegant, you can remove the "dp" array. If you want to keep track of the full list, then you only need to keep track of "dpl". Here is code that I wrote and it works:

  n = 10
  denom = [1, 3, 4]
  dpl = [[] for i in range(n+1)]
  def f(n):
      if dpl[n]:
          return dpl[n]
  
      if n <= 0:
          return []

      ans = list(range(n))  # this is the max size possible
      for i in denom:
          if n-i >= 0:
              new = f(n-i) + [i]  # append i to the end of the array
              if len(new) <= len(ans):
                  ans = new

      dpl[n] = ans
      return ans

  if __name__ == "__main__":
      sol = f(n)
      print(sol)


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: