wzq0428

题解

/ 注册

全部文章 / 题解（共1篇）

时间空间复杂度均为O(n)的解法

emmm，一不小心捣鼓出来一个O(n)的算法…… 用数组count[i]来存储能组合出i的方案数。一共四种硬币，从1元开始，依次考虑，比如说，只用1元来组合，显然每个i都只有一种组合方案。现在考虑加入2元，我们事先约定小的硬币在前，大的硬币在后，那么count[i]至少由一个2元硬币组成的情况下...

动态规划

2019-09-26

3 909