solve <- function(v, S)
{
    f <- function(s)
    {
        if (s < 0) return(Inf)
        if (s == 0) return(0)
        ifelse(N[s], N[s], N[s] <<- min(Vectorize(f)(s - v)) + 1)
    }
 
    N <- rep(0, S)
    ifelse((n <- f(S)) == Inf, -1, n)
}
 
printf <- function(...) cat(sprintf(...))
 
for (v in list(c(1, 7, 10), c(3, 7, 10))) {
    printf("硬貨が[%s]のとき\n", toString(v))
    printf("　金額 → 使用枚数\n")
    for (S in 1:20) printf("　%d → %d\n", S, solve(v, S))
    printf("\n")
}

c29sdmUgPC0gZnVuY3Rpb24odiwgUykKewogICAgZiA8LSBmdW5jdGlvbihzKQogICAgewogICAgICAgIGlmIChzIDwgMCkgcmV0dXJuKEluZikKICAgICAgICBpZiAocyA9PSAwKSByZXR1cm4oMCkKICAgICAgICBpZmVsc2UoTltzXSwgTltzXSwgTltzXSA8PC0gbWluKFZlY3Rvcml6ZShmKShzIC0gdikpICsgMSkKICAgIH0KCiAgICBOIDwtIHJlcCgwLCBTKQogICAgaWZlbHNlKChuIDwtIGYoUykpID09IEluZiwgLTEsIG4pCn0KCnByaW50ZiA8LSBmdW5jdGlvbiguLi4pIGNhdChzcHJpbnRmKC4uLikpCgpmb3IgKHYgaW4gbGlzdChjKDEsIDcsIDEwKSwgYygzLCA3LCAxMCkpKSB7CiAgICBwcmludGYoIuehrOiyqOOBjFslc13jga7jgajjgY1cbiIsIHRvU3RyaW5nKHYpKQogICAgcHJpbnRmKCLjgIDph5HpoY0g4oaSIOS9v+eUqOaemuaVsFxuIikKICAgIGZvciAoUyBpbiAxOjIwKSBwcmludGYoIuOAgCVkIOKGkiAlZFxuIiwgUywgc29sdmUodiwgUykpCiAgICBwcmludGYoIlxuIikKfQ==