HackerRank The Coin Change Problem
https://www.hackerrank.com/challenges/coin-change/problem
解答
code: python
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'getWays' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts following parameters:
# 1. INTEGER n
# 2. LONG_INTEGER_ARRAY c
#
def getWays(n, c):
# Write your code here
# m = len(c)
# dp = [0 * (n+1) for _ in range(m+1)]
# for i in range(m+1):
# dpi0 = 1
# for i in range(1, m+1):
# for j in range(1, n+1):
# if i > 1:
# dpij += dpi-1j
# if j >= ci-1:
# dpij += dpi[j-ci-1]
# return dpmn
m = len(c)
dp = 0 * (n+1)
dp0 = 1
# 1, 0, 0, 0, 0
# 1, 1, 1, 1, 1
# 1, 1, 2, 2, 3
# 1, 1, 2, 3, 4
for i in range(1, m+1):
for j in range(ci-1, n+1):
dpj += dp[j-ci-1]
return dpn
if __name__ == '__main__':
fptr = open(os.environ'OUTPUT_PATH', 'w')
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input0)
m = int(first_multiple_input1)
c = list(map(int, input().rstrip().split()))
# Print the number of ways of making change for 'n' units using coins having the values given by 'c'
ways = getWays(n, c)
fptr.write(str(ways) + '\n')
fptr.close()
テーマ
#dp
メモ
https://www.youtube.com/watch?v=XR9m3FCF9rs