We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #114: Counting block combinations I
  4. Discussions

Project Euler #114: Counting block combinations I

  • doudoudou
     + 1 comment

    Hi, I have tried this problem a few times and keep failing due to timeout (a bit frustrating). Here's my code which runs O(n). It is based on the idea that f(n) = 2* f(n-1) - f(n-2) + f(n-m-1). Can someone give any hint what would be a better solution? 

    def f(n, m):
    if n < m: return 1
    if n == m: return 2

    a = [1] * (m + 1)
    a[m] = 2
    value, p = 0, 0
    for _ in range(m + 1, n + 1):
        value = 2 * a[(p+m) % (m+1)] - a[(p+m-1) % (m+1)] + a[p]
        a[p] = value
        p = (p+1) % (m+1)
    return value