$0$ 円以上 $x$ 円以下の良い金額を数えれば良いです。 $N = 1$ は奇数の数を数えれば良いです。 $N \geq 2$ を考えます。
公式解説のように上の紙幣から貪欲に払っていけば良いです。よって、 $2A_N$ ごとに周期を考えられます。 $2A_N$ で割った余りが $[0, A_N)$ ならば $N := N - 1, A := (A_1, A_2, \dots, A_{N-1})$ として再帰できて、 $[A_N, 2A_N)$ ならば良い金額です。

すなわち以下のような疑似コードで考えられます。

def solve(n, x, a):
    if n == 1:
        return (x + 1) // 2
    
    res = (solve(n - 1, a[n - 1] - 1, a) + a[n - 1]) * (x / (2 * a[n - 1]))
    y = x % (2 * a[n - 1])
    res += solve(n - 1, min(y, a[n - 1] - 1), a) + max(0, y - a[n - 1] + 1)

    return res

これをメモ化再帰すれば良いです。計算量は $O(N \log N)$ です。

余談: 日本では「割り切れない」ということで奇数の金額はご祝儀などで包む金額として適しているとされており、本問の問題名はそれを基にしています。