Domino Effect Problem Last week we had a programming contest in my university and I am very curious about one of the problems , one which only one team (but from another city) was able to solve. Maybe its not that hard, but I cant find any solutions that will take less than a second of execution time. The problem is the following:

Problem

You have N domino tiles separated by different amounts (integer values that are given to you) and you know the height H of these tiles (all have the same height). They are all placed standing up so that if you push one it falls in the direction of the next one. This way, if tile I is close enough (H or less) to tile I+1, the first one will push the second one when it is pushed down, producing the domino effect. Suppose that not all the distances that separate the tiles are smaller than H, what's the minimum amount of moves you need to make in order to have all the distances be at most H? You can't move the first nor the last tile. Print a falsey value if it is not possible.

Note: You are only allowed to move integer amounts and only to spots on the line defined by tile i-1 and tile i+1. This means you cant grab one and place it wherever you want.

Here are the input sizes: (3 ≤ N ≤ 1000) (1 ≤ H ≤ 50)  and the distances (1 ≤ Di ≤ 100 for i = 1, 2, ..., N-1). Someone uploaded it to SPOJ recently


  Input:
  
  N H
  
  d1 d2 d3 d4 ... d(n-1)
  
  Output:
  
  Minimum amount of moves.


Sample


  Input1
  
  8 3
  
  2 4 4 1 4 3 2
  
  Output1
  
  3


Sample2


  Input2
  
  10 2
  
  1 2 2 2 2 2 2 2 3
  
  Output2
  
  8


Sample3


  Input3
  
  5 2
  
  2 2 2 2
  
  Output3
  
  0


Sample4


  Input4
  
  5 3
  
  1 6 2 4
  
  Output4
  
  -1 (NOT POSSIBLE)


I have only found a good solution for two cases (Pseudo-Code):

D=sum_of_all_distances
MaxPossible=(N-1)*H

if D==MaxPossible and there is no di such that di&gt;H
    Answer=0

else if D&gt;MaxPossible
    Answer=-1
Python

N, H = map(int, raw_input().split())
D = map(int, raw_input().split())

# map from (number of dominoes, distance to last domino) to                                                                                                        
# the number of moves needed to adjust the first number of dominoes                                                                                                
# exactly that far.                                                                                                                                                
M = {}
M[1,0] = 0

for i in xrange(2, N+1):      # i = number of dominos to try                                                                                                       
  for d in xrange(H*(i-1)+1):
    M[i,d] = 1e9
  for d in xrange(H*(i-1)+1): # position of last domino                                                                                                            
    for e in xrange(1, H+1):  # distance from last domino to previous one                                                                                          
      if d-e &gt; H*(i-2): continue
      if d-e &lt; 0: continue
      if sum(D[:i-1]) == d:
        # don't move last domino, arrange rest                                                                                                                     
        M[i,d] = min(M[i,d], M[i-1,d-e])
      else:
        # arrange rest, move last domino to right location                                                                                                         
        M[i,d] = min(M[i,d], 1 + M[i-1,d-e])

print M.get((N,sum(D)), -1)


Standard dynamic programming.  Runs pretty much instantaneously on the example inputs.  How big a problem do we have to solve in under a second?