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)