Q1.
输入一串数字和一个目标值，求解不重复的使用这串数字中的数能够有多少种得到目标值的方法。
如使用12234求解目标值5，则：
1+2+2 = 5；
2+3 = 5；
2（另一个2）+3 = 5；
1+4 = 5
总共有4种方式。
思路：按顺序排查输入的这串数字，每一个数字都有两种情况：使用其形成目标数字，不使用其形成目标数字。使用recursion可以容易求解：
def solve(input_number, target_sum):
if input_number == 0:
#input_number为0就是判断到了这串数字的最后一个，所以属于base condition
if target_sum == 0:
return 1
#如果target_sum等于0，说明之前选择的路径能够得到目标值，所以形成一个解，返回数字1代表一个解
return 0
if target_sum < 0:
return 0
#还会出现一些路径值求和大于了目标值，这样的情况不是解，不用继续向下展开，返回数字0代表无解
return solve(input_number // 10, target_sum) + solve(input_number // 10, target_sum - input_number % 10)
#对于每一位数字都有两种基本情况，使用/不使用这个数字作为求目标值的一部分
Q2.
同样的道理，把上题中求和得到目标值替换为求积得到目标值：
def solve(input_number, target_product):
if input_number == 0:
if target_product == 1:
return 1
return 0
if target_product % (input_number % 10) == 0:
return solve(input_number // 10, target_product) + solve(input_number // 10, target_product // (input_number % 10))
else:
return solve(input_number // 10, target_product)
#与求和不同，任何数字都可以选择使用/不使用它来求和；但是乘积要先判断能不能整除，如果不能整除就一定不能使用
Q3.
在Q1的基础上继续变形，把返回具体的解法数量，换成由哪些解组成的。
def solve(input_number, target_sum):
if input_number == 0:
if target_sum == 0:
return [[]]
#如果有解，则返回一个嵌套的list结构，在内层可以生成之前路径使用的数字
return []
#如果无解，则返回一个不嵌套的list，无法在内层list生成解
if target_sum < 0:
return []
return solve(input_number // 10, target_sum) + \
[[input_number % 10] + sol for sol in solve(input_number // 10, target_sum - input_number % 10)]
#这条语句不容易理解，核心是两个加号，这两个加号的共同点为二者都是list的连接符；
#不同点是，第一个加号是不同解之间的list连接，第二个加号是形成解过程的list连接
#换句话说，第一个加号连接的是外层的list element，第二个加号连接的内层的list element
print(solve(12345, 5))
>>>
[[2, 2, 1], [3, 2], [3, 2], [4, 1]]
Q4.
在Q3的基础上，去除重复的解。
def solve_without_duplication(input_number, target_sum):
solutions = []
for sol in solve(input_number, target_sum):
sorted_sol = sorted(sol)
if sorted_sol not in solutions:
solutions.append(sorted_sol)
return solutions
这段程序的操作比较简单，没有注释。
Q5.
继续在Q1的基础上变形，输入一串字母，找到其中增长的字母串的最大长度，允许不连续。比如'aceh'，它的最大增长长度就是4；'caeh'，它的最大增长长度就是3（aeh）。
def longest_increasing_sequence(w):
for target_length in range(len(w), 0, -1):
n = nb_of_sol(w, target_length, 0, chr(ord('a') - 1))
if n:
return target_length
#因为要找最大程度，所以逆序去找，最大可能是word的长度，最短是1，这就有了上面的for循环
#使用nb_of_sol根据输入的word，指定的长度，index和最后一个character寻找符合要求的解，有解救返回这个targe_length值
#使用比ord('a')小1作为最后一个字母的初始值，保证任意一个字母都可以作为第一个开头字母使用
def nb_of_sol(w, desired_length, index, last_char):
if desigred_length == 0:
return 1
if index >= len(w):
return 0
if w[index] > last_char:
return nb_of_sol(w, desired_length - 1, index + 1, w[index]) +\
nb_of_sol(w, desired_length, index + 1, last_char)
#也是分成是否使用该字母构建目标值，不管是否使用index都要加1，和之前输入数字串要//10是一个道理
#如果使用这个字母，则length要减1，同时最后的字母变成当前最后一个字母，方便判断后续字母是否比这个大
else:
return nb_of_sol(w, desired_length, index + 1, last_char)
