题目描述

python 版

n = int(input())
shu = [0,10,20,50,100]
## 二维
# dp = [[0]*(n+1) for i in range(len(shu))]
# for i in range(len(shu)):
#     dp[i][0] = 1

# for i in range(1,len(shu)):
#     for j in range(1,n+1):
#         dp[i][j] = dp[i-1][j]
#         if j >= shu[i]:
#             dp[i][j] = dp[i][j] + dp[i][j-shu[i]]
# print(dp[-1][-1])

# 一维优化
dp= [0 for i in range(n+1)]
dp[0] = 1
for i in range(1,len(shu)):
    for j in range(1,n+1):
        if j >= shu[i]:
            dp[j] = dp[j] + dp[j-shu[i]]
print(dp[-1])