消费的最小路径

Minimum path to consume

假设有150张优惠券可以消费
在每次迭代中有 3 种消耗它们的方法 - 一次 15 次,一次 1 次或每次恰好一半。
很明显,一张券只能全额消费
我们需要找出优惠券 运行 下降到 0 的最短路径(迭代次数)。
暴力破解是唯一的出路吗?
或者我们是否有解决这种情况的算法。

这可以在 Dynamic Programming (DP) 中通过以下递归公式解决:

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

在自下而上的 DP 中,它将类似于:(伪代码)

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]