“Coin-change”问题是指给定一定数量的不同硬币面值,要求找到以最少的硬币数量组成给定金额的方案。这个问题可以用递归或动态规划来解决,但都存在时间复杂度较高和内存占用较大的问题。
为了解决这个问题,可以使用“hylo”解决方案。Hylo是一种组合了递归和动态规划思想的解决方案,可以在避免资源浪费的情况下,以优秀的时间复杂度解决该问题。
下面给出具体的代码实现:
{-# LANGUAGE DeriveFunctor #-}
data Cofree f a = a :< f (Cofree f a)
deriving Functor
anaC :: Functor f => (a -> f a) -> (a -> Cofree f b) -> a -> Cofree f b
anaC psi phi z = case phi z of
b :< fz -> b :< fmap (anaC psi phi) (psi z)
type ListF a x = Maybe (a, x)
toListF :: [a] -> ListF a [a]
toListF [] = Nothing
toListF (x:xs) = Just (x, xs)
coinChange :: [Int] -> Int -> Maybe [Int]
coinChange coins amount = reduce res
where
res = anaC (toListF . select coins amount) (phi coins) amount
phi :: [Int] -> Int -> ListF Int Int
phi coins 0 = Nothing
phi coins n = case mfilter (<= n) coins of
[] -> Nothing
(c:cs) -> Just (c, n-c)
select :: [Int] -> Int -> [Int] -> [Int]
select coins n [] = []
select coins n (x:xs) | n < x = select coins n xs
| otherwise = x : select coins (n-x) (x:xs)
reduce ::