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

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