[Solved] Minimum path to consume

by


This can be solved in Dynamic Programming (DP) by following the recursive formula:

D(x) = INFINITY x < 0
D(0) = 0
D(x) = min{ D(x-1), D(x-15), D(x/2) } + 1

In bottom-up DP it will be something like: (pseudo code)

D = new int[151]
D[0] = 0
for (int i = 1; i <151; i++) {
   best = min(D[i-1], D[i/2]) //add floor or ceil according to definition of problem to i/2
   if (i >= 15): 
      best = min(best, D[i-15])  
   D[i] = best + 1
}
return D[150]

2

solved Minimum path to consume