thay đổi Đếm trong Haskell

Question

tôi đi qua các giải pháp sau để vấn đề DP của counting change:

count' :: Int -> [Int] -> Int 
count' cents coins = aux coins !! cents 
    where aux = foldr addCoin (1:repeat 0) 
      where addCoin c oldlist = newlist 
        where newlist = (take c oldlist) ++ zipWith (+) newlist (drop c oldlist) 

Nó chạy nhanh hơn rất nhiều so với giải pháp đệ quy trên xuống ngây thơ của tôi, và tôi vẫn đang cố gắng để hiểu nó.

Tôi nhận được danh sách tiền xu, aux tính toán mọi giải pháp cho các số nguyên dương. Vì vậy, giải pháp cho một số tiền là lập chỉ mục danh sách tại vị trí đó.

Tôi ít rõ ràng hơn vào addCoin. Nó bằng cách nào đó sử dụng giá trị của mỗi đồng tiền để rút ra các yếu tố từ danh sách tiền xu? Tôi đang đấu tranh để tìm một ý nghĩa trực quan cho nó.

Lần in trong aux cũng liên kết bộ não của tôi bằng nút thắt. Tại sao 1:repeat 0 giá trị ban đầu? Nó đại diện cho cái gì?

Answer 1

Đó là một bản dịch trực tiếp của thuật toán DP bắt buộc cho các vấn đề, mà trông như thế này (bằng Python):

def count(cents, coins): 
    solutions = [1] + [0]*cents # [1, 0, 0, 0, ... 0] 
    for coin in coins: 
     for i in range(coin, cents + 1): 
      solutions[i] += solutions[i - coin] 
    return solutions[cents] 

Đặc biệt, addCoin coin solutions tương ứng với

for i in range(coin, cents + 1): 
    solutions[i] += solutions[i - coin] 

ngoại trừ việc addCoin lợi nhuận danh sách được sửa đổi thay vì thay đổi danh sách cũ. Đối với phiên bản Haskell, kết quả sẽ có phần không đổi ở đầu cho đến khi phần tử coin thứ và sau đó chúng ta phải triển khai solutions[i] += solutions[i - coin].

Chúng tôi nhận thấy phần không đổi theo take c oldlist và phần được sửa đổi theo zipWith (+) newlist (drop c oldlist). Trong phần đã sửa đổi, chúng tôi cộng các phần tử i -th vào danh sách cũ và i - coin -th phần tử của danh sách kết quả. Việc dịch chuyển các chỉ số là ẩn trong các hoạt động drop và take.

Một đơn giản, ví dụ điển hình cho các loại hình chuyển dịch và định nghĩa đệ quy là số Fibonacci:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 

Chúng tôi sẽ viết này phải nhất thiết như

def fibs(limit): 
    res = [0, 1] + [0]*(limit - 2) 
    for i in range(2, limit): 
     res[i] = res[i - 2] + res[i - 1] 
    return res 

Quay trở lại sự thay đổi xu, foldr addCoin (1:repeat 0) tương ứng để khởi tạo solutions và vòng lặp for trên các đồng tiền, với sự thay đổi danh sách ban đầu là vô hạn thay vì hữu hạn (vì sự lười biếng cho phép chúng ta làm điều đó).