- 科技
- leetcode：322. 零钱兑换（dp，背包，中等）
题目：
分析：典型的背包问题，不过被数据范围吓到了：
题解直接vector dp(amount+1,amount+1)
这个初始化是很妙的，因为使用的最大可能个数是：amount。
代码：
class Solution {
public:
int coinChange(vector
<int>& c
, int amount
) {
vector
<int> dp(amount
+1,amount
+1);
dp
[0]=0;
for(int i
=0;i
<c
.size();i
++)
{
for(int j
=c
[i
];j
<=amount
;j
++)
{
dp
[j
]=min(dp
[j
],1+dp
[j
-c
[i
]]);
}
}
if(dp
[amount
]==amount
+1) return -1;
return dp
[amount
];
}
};
Processed:
0.009, SQL:
8
