硬币兑换方案总数（动态规划）

import pandas as pd

# S = 4

# coins = [1, 2, 3] # 假设都是从小到大排序

S = 10

coins = [2, 3, 5, 6]

DP = [[0 for x in range(S)] for _ in range(len(coins))]

def init():

# 第一行初始化

for j in range(S):

if (j + 1) % coins[0] == 0: # 此处默认coins[0]为最小面值

DP[0][j] = 1

# 第一列不需要初始化

def dynamic():

for j in range(S): # 列

for i in range(1, len(coins)): # 行，从第二行开始

if j + 1 - coins[i] < 0:

xx = 0

elif j + 1 - coins[i] == 0:

xx = 1

else:

xx = DP[i][j - coins[i]]

DP[i][j] = DP[i - 1][j] + xx

if __name__ == '__main__':

init()

dynamic()

print((DP))