1. Dynamic Programming(DP)

继续讲解动态规划的思考问题，把一个大的问题拆解成子问题，寻找最优路径解决。是recursion和iteration的替代解法，Eric课上使用了levenshein distance作为例子解释，PDF已经详细说明。

2. DP练习1

Lab6-Q1：Obtaining a sum from a subsequence of digits
Write a program sum_of_digits.py that prompts the user for two numbers, say available_digits and desired_sum, and outputs the number of ways of selecting digits from available_digits that
sum up to desired_sum. For 4 solutions:
--one solution is obtained by selecting 1 and both occurrences of 2 (1 + 2 + 2 = 5);
--one solution is obtained by selecting 1 and 4 (1 + 4 = 5);
--one solution is obtained by selecting the first occurrence of 2 and 3 (2 + 3 = 5);
--one solution is obtained by selecting the second occurrence of 2 and 3 (2 + 3 = 5).

#DP solution:
#available_digits = 1 2 2 3 4, sum = 5
#   1    2    3    4    5 (sum)
#1 1,1  1,1  1,1  1,1  1,1 (第一个数字是sum值，第二个数字是路径数量)
#2 1,1  2,1  3,1  3,1  3,1 
#2 1,1  2,2  3,2  4,1  5,1
#3 1,1  2,2  3,3  4,2  5,3
#4 1,1  2,2  3,3  4,3  5,4
#digits

#digits = [1, 2, 2, 3, 4]
#default: cell[0] = digits[0] * sum
##cell[i][j] = max(cell[i - 1][j], cell[i - 1][j - digits[i]] + digits[i])
##路径数量分情况讨论，如下面的代码，如果本行的digits数值与某个cell中上一行同一位置的数值相等，则本行这个cell中的路径数量等于上一行对应位置的路径数量加1
#def printcell():
#    for i in range(nrow):
#        for j in range(ncolumn):
#            print(cell[i][j], end = ' ')
#        print()


digits = input('Input a number that we will use as available digits: ')
desired_sum = int(input('Input a number that represents the desired sum: '))

digits = [int(e) for e in sorted(digits)]
nrow = len(digits)
ncolumn = desired_sum
cell = [[[0, 0] for _ in range(ncolumn)] for _ in range(nrow)]
#创建一个网格，行数等于输入的可用数字的长度，列数等于输入的总和，也就是说以1为步长构建column。网格default值为0，以及一个记录path组成方式数量的空list
for j in range(ncolumn):
    if j + 1 >= digits[0]:
        cell[0][j][0] = digits[0]
        cell[0][j][1] = 1
    else:
        cell[0][j][0] = 0
        cell[0][j][1] = 0
#创建第一行的default值，如果比某列sum值大则设置为0，否则则设置为digits第一个值
for i in range(1, nrow):
    for j in range(ncolumn):
        if digits[i] > j + 1:
            cell[i][j][0] = cell[i - 1][j][0]
            cell[i][j][1] = cell[i - 1][j][1]
        elif digits[i] == j + 1:
            cell[i][j][0] = digits[i]
            if cell[i - 1][j][0] == digits[i]:
                cell[i][j][1] = cell[i - 1][j][1] + 1          
            else:
                cell[i][j][1] = 1
        else:
            a = cell[i - 1][j][0]
            b = cell[i - 1][j - digits[i]][0] + digits[i]
            if a == b:
                cell[i][j][0] = a
                cell[i][j][1] = cell[i - 1][j][1] + cell[i - 1][j - digits[i]][1]
            else:
                if a > b:
                    cell[i][j][0] = a
                    cell[i][j][1] = cell[i - 1][j][1]
                else:
                    cell[i][j][0] = b
                    cell[i][j][1] = cell[i - 1][j - digits[i]][1]
#    printcell()

if cell[-1][-1][0] == desired_sum:
    solution = cell[-1][-1][1]
else:
    solution = 0
    
if solution == 0:
    print('There is no solution.')
elif solution == 1:
    print('There is a unique solution.')
else:
    print('There are %d solutions.' % solution)

DP练习2

Lab7-Q1：Write a program greedy_change.py that prompts the user for an amount, and outputs the minimal number of banknotes needed to yield that amount, as well as the detail of how many banknotes of each type value are used. The available banknotes have a face value which is one of $1, $2, $5, $10, $20, $50, and $100.
当下的写法思路上没有太大问题，完全DP解法，但是有太多判断，不够好，需要再思考如何优化判断问题：

desired_amount = int(input('Input the desired amount: '))

default_record = {1:0, 2:0, 5:0, 10:0, 20:0, 50:0, 100:0}
min_number = [[0, default_record.copy()] for _ in range(desired_amount + 1)]
#初始化所有的amount，每一个是一个list，[min_number = 0, record = default_record]
def count_number(dic):
    total = 0
    for i in dic:
        total += dic[i]
    return total
#count字典中所有key的value和

for i in range(1, desired_amount + 1):
    candidate = []
    if i >= 1:
        record1 = min_number[i - 1][1].copy()
        record1[1] += 1
        number1 = count_number(record1)
        candidate.append(number1)
    if i >= 2:
        record2 = min_number[i - 2][1].copy()
        record2[2] += 1
        number2 = count_number(record2)
        candidate.append(number2)
    if i >= 5:
        record5 = min_number[i - 5][1].copy()
        record5[5] += 1
        number5 = count_number(record5)
        candidate.append(number5)
    if i >= 10:
        record10 = min_number[i - 10][1].copy()
        record10[10] += 1
        number10 = count_number(record10)
        candidate.append(number10)
    if i >= 20:
        record20 = min_number[i - 20][1].copy()
        record20[20] += 1
        number20 = count_number(record20)
        candidate.append(number20)
    if i >= 50:
        record50 = min_number[i - 50][1].copy()
        record50[50] += 1
        number50 = count_number(record50)
        candidate.append(number50)
    if i >= 100:
        record100 = min_number[i - 100][1].copy()
        record100[100] += 1
        number100 = count_number(record100)
        candidate.append(number100)

    minimum = min(candidate)
    if i < 2:
        min_number[i][1] = record1
    elif i < 5:
        if number2 == minimum:
            min_number[i][1] = record2
        elif number1 == minimum:
            min_number[i][1] = record1
    elif i < 10:
        if number5 == minimum:
            min_number[i][1] = record5
        elif number2 == minimum:
            min_number[i][1] = record2
        elif number1 == minimum:
            min_number[i][1] = record1
    elif i < 20:
        if number10 == minimum:
            min_number[i][1] = record10
        elif number5 == minimum:
            min_number[i][1] = record5
        elif number2 == minimum:
            min_number[i][1] = record2
        elif number1 == minimum:
            min_number[i][1] = record1
    elif i < 50:
        if number20 == minimum:
            min_number[i][1] = record20
        elif number10 == minimum:
            min_number[i][1] = record10
        elif number5 == minimum:
            min_number[i][1] = record5
        elif number2 == minimum:
            min_number[i][1] = record2
        elif number1 == minimum:
            min_number[i][1] = record1
    elif i < 100:
        if number50 == minimum:
            min_number[i][1] = record50
        elif number20 == minimum:
            min_number[i][1] = record20
        elif number10 == minimum:
            min_number[i][1] = record10
        elif number5 == minimum:
            min_number[i][1] = record5
        elif number2 == minimum:
            min_number[i][1] = record2
        elif number1 == minimum:
            min_number[i][1] = record1
    else:
        if number100 == minimum:
            min_number[i][1] = record100
        elif number50 == minimum:
            min_number[i][1] = record50
        elif number20 == minimum:
            min_number[i][1] = record20
        elif number10 == minimum:
            min_number[i][1] = record10
        elif number5 == minimum:
            min_number[i][1] = record5
        elif number2 == minimum:
            min_number[i][1] = record2
        elif number1 == minimum:
            min_number[i][1] = record1
    min_number[i][0] = count_number(min_number[i][1]) 
    #print(i, min_number)

number = min_number[-1][0]
if number == 1:
    print('%d banknote is needed.' % number)
else:
    print('%d banknote are needed.' % number)

output = []
for i in min_number[-1][1]:
    if min_number[-1][1][i] != 0:
        output.append((i, min_number[-1][1][i]))
output.sort(reverse = True)

for i in output:
    print(' ' * (4 - len(str(i[0]))), '$%d' % i[0], ': ', '%d' % i[1], sep = '')