# def read_ints return int value for value in input split Banknotes tota

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53``` ```def read_ints(): return [int(value) for value in input().split()] # Banknotes total = int(input()) banknotes = [int(value) for value in input().split()] dp = [0] + [float('inf')] * total for amount in range(total + 1): for banknote in banknotes: if amount >= banknote: dp[amount] = min(dp[amount], 1 + dp[amount - banknote]) print(dp[total]) # LIS a = [3, -1, 3, -2, 0, 5, 7, 2, 5, 2] dp = [1] * len(a) for i in range(len(a)): for j in range(i): if a[j] < a[i] and dp[i] < dp[j] + 1: dp[i] = dp[j] + 1 print(max(dp)) # LCS a, b = read_ints(), read_ints() n, m = len(a), len(b) lcs = [[0] * (m + 1) for i in range(n + 1)] for i in range(n): for j in range(m): if a[i] == b[j]: lcs[i][j] = lcs[i - 1][j - 1] + 1 else: lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]) answer = [] i, j = n - 1, m - 1 while i != -1 and j != -1: if a[i] == b[j]: answer.append(a[i]) i -= 1 j -= 1 elif lcs[i - 1][j] > lcs[i][j - 1]: i -= 1 else: j -= 1 print(answer[::-1]) ```