step2:遍历coins列表找出小于金额的硬币面值
j
j
j，接着再使用
d
p
[
i
−
c
o
i
n
s
[
j
]
]
dp[i-coins[j]]
dp[i−coins[j]]来找出
i
−
c
o
i
n
s
[
j
]
i-coins[j]
i−coins[j]的最优解;最终金额
i
i
i的最优解为
1
+
d
p
[
i
−
c
o
i
n
s
[
j
]
]
1+dp[i-coins[j]]
1+dp[i−coins[j]]。
d
p
[
1
]
=
d
p
[
0
]
+
1
=
1
dp[1]=dp[0]+1=1
dp[1]=dp[0]+1=1
d
p
[
2
]
=
d
p
[
0
]
+
2
dp[2]=dp[0]+2
dp[2]=dp[0]+2、
d
p
[
2
]
=
d
p
[
1
]
+
1
dp[2]=dp[1]+1
dp[2]=dp[1]+1，而
d
p
[
0
]
<
d
p
[
1
]
dp[0]<dp[1]
dp[0]<dp[1]，故
d
p
[
2
]
=
d
p
[
0
]
+
2
=
1
dp[2]=dp[0]+2=1
dp[2]=dp[0]+2=1
d
p
[
3
]
=
1
+
d
p
[
2
]
dp[3]=1+dp[2]
dp[3]=1+dp[2]、
d
p
[
3
]
=
2
+
d
p
[
1
]
dp[3]=2+dp[1]
dp[3]=2+dp[1]，而
d
p
[
1
]
=
d
p
[
2
]
=
1
dp[1]=dp[2]=1
dp[1]=dp[2]=1，故
d
p
[
3
]
=
1
+
1
=
2
dp[3]=1+1=2
dp[3]=1+1=2
d
p
[
4
]
=
1
+
d
p
[
3
]
dp[4]=1+dp[3]
dp[4]=1+dp[3]、
d
p
[
4
]
=
2
+
d
p
[
2
]
dp[4]=2+dp[2]
dp[4]=2+dp[2]，而
d
p
[
2
]
<
d
p
[
3
]
dp[2]<dp[3]
dp[2]<dp[3]，故
d
p
[
4
]
=
2
dp[4]=2
dp[4]=2
d
p
[
5
]
=
d
p
[
0
]
+
1
=
1
dp[5]=dp[0]+1=1
dp[5]=dp[0]+1=1
d
p
[
6
]
=
1
+
d
p
[
5
]
dp[6]=1+dp[5]
dp[6]=1+dp[5]、
d
p
[
6
]
=
2
+
d
p
[
4
]
dp[6]=2+dp[4]
dp[6]=2+dp[4]、
d
p
[
6
]
=
5
+
d
p
[
1
]
dp[6]=5+dp[1]
dp[6]=5+dp[1]
同理，计算出剩下所有金额的最优解：