2293.コイン1
4646 ワード
質問する
白駿2293号硬貨1
に答える
考えもせずにdfsで解決した.間違いなく
RecursionErrorを受けた.今はdfsのトラウマを起こしたい.
def dfs(L, val):
global cnt
if val == k:
cnt += 1
if val > k or val+coins[L] > k: return
else:
for i in range(L, len(coins)):
dfs(i, val + coins[i])
if __name__ == '__main__':
n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
cnt = 0
dfs(0, 0)
print(cnt)
動的な配置は、次のように求めることができます.
スペース効率を向上させるために、更新には2 Dリストではなく1 Dリストが使用されます.
n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
dy = [0] * (k+1)
for c in coins:
for i in range(c, k+1):
dy[i] = dy[i] + dy[i-c] if i-c > 0 else dy[i] + 1
print(dy[k])足りないところ
これは基本的な問題ですが、アルゴリズム全体では真実ではありません.
基本アルゴリズムを習得するためには,繰り返し実現することによって習得する必要がある.
Reference
この問題について(2293.コイン1), 我々は、より多くの情報をここで見つけました https://velog.io/@kimsen/2293.-동전1テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol