algorithm - 动态规划算法 - 花费 A 美元的方法数

Question

我对如何处理这个动态算法问题感到困惑——我想把问题分解成更小的子问题，但我不知道该怎么做

问题：假设您正在购物并计划花费 A 美元。您对 t 件物品感兴趣，每件物品供应无限，因此价值 C1、C2、...、Ct 美元。设计一个动态规划算法来计算花费 A 美元的方式的数量。

任何帮助将不胜感激！

标签： algorithmdynamic-programming

Answer 1

I would create an array size + 1 of A.Then iterate on it and inside in iterate the items on increment the value at index you reach by the value where you were.

Let's say A is 4 the array will be all 0. arr = [0 , 0 ,0 ,0 , 0] and item are 1 and 2 dollars.

at step one arr will become [0,1,1,0,0]
step two [0,1,2,1,0] 
3 [0,1,2,3,1]
4 [0,1,2,3,4]

And I highly recommend you to check out this question https://www.geeksforgeeks.org/coin-change-dp-7/