动态规划例题

动态规划就是把一个复杂的问题分拆为几个小问题，一步步求解。

1. 求最长连续增长子序列。

给出一个数列，输出最长连续增长序列个数。比如[1,2,3,8,5,7,0,4,2] 输出结果为4，即序列[1,2,3,8]。只要输出个数就行，不用输出子序列。
这个问题就比较复杂，第一不知道子序列从哪个数开始，第二也不知道子序列在哪个数结束。只有知道开始结束后才能求出其长度。
（1）不知道子序列以哪个数结尾那就把以每个元素结尾的最长连续增长序列长度都算出来，再找出最大值便可。
（2）现在已知序列的结尾，要找也开头了，但其实不用管开头是什么，因为只要求出序列的长度就可以了。所以只要看前面一个数比当前数字大还是小就可以了。比如以7结尾的序列，前面一个数5比7小，所以以7结尾的比以5结尾的序列大1。否则只能是自己一个数，长度为1.比如以0结尾的最长连续增长子序列就是[0].
(3) 求出以每个元素结尾的最长连续增长子序列后找出最大的即可。

nums = [1,2,3,8,5,7,0,4,2]

def endLength(index):
    if index == 0:
        return 1
    current_num = nums[index]
    if current_num > nums[index -1]:
        return endLength(index -1) + 1
    else:
        return 1

result_list = []
for i in range(len(nums)):
    result = endLength(i)
    result_list.append(result)

max_length = max(result_list)
print(max_length)

这样可以得出结果，但用了递归。由于求后面一个数要利用前一个数的结果，每次重新计算导致时间复杂度增加。因此可以将结果保存下来加以利用。

def max_inc_length(arr):
    if not arr:
        return 0
    length_list = [1] * len(arr)
    for i in range(1, len(arr)):
        if arr[i] > arr[i-1]:
            length_list[i] = length_list[i-1] + 1
    return max(length_list)

无论以哪个数结尾的最长连续增长序列其长度至少是1，所以先统一初始化为1，然后它比前一个数大则在其结果上加1，否则就是1，不用做更改。

2. 求最长增长序列
   这个与上一题类似，只是不要求子序列是连续的。这样的话知道子序列的结尾，那么前一个数就有可能是在它之前所有比它小的数。比如[1, 2, 3, 8, 5, 7, 0, 4, 2, 9, 4, 5]以7结尾的最长增长序列倒数第二个数可能是它之前的5，或3，或2，或1。所以假设每个在它之前比它小的数都为子序列倒数第二个数，找出最大的哪个。

def max_inc_length(arr):
    if not arr:
        return 0
    length_list = [1] * len(arr)
    for i in range(1, len(arr)):
        for j in range(i):
            if arr[i] > arr[j]:
                length_list[i] = max(length_list[j] + 1, length_list[i])
    return max(length_list)

3. 最少钱币找零
   有1元，5元，8元的钱币，需要找零y元，求最少用几张钱币。
   一种思路是先用8元的凑，剩余金额小于8元时用5元最后用一元，但在这不适用。比如11元，按上需思路要用1张8元3张1元共4张，实际用2张5元和1张1元只需要3张。
   要凑够11元肯定要先凑够10元，6元或3元，然后再加1张就是11元了。所以问题就成了凑够10元，6元或3元最少用几张了，这样就把一个凑较大金额的问题变成了3个凑较小金额的问题，依此类推便可求解。

def min_note_number(amount):
    amount = int(amount)
    if amount <= 0:
        return 0
    if amount == 1:
        return 1
    if amount >= 8:
        return 1 + min(min_note_number(amount-8),min_note_number(amount-5),min_note_number(amount-1))
    if amount >= 5:
        return 1 + min(min_note_number(amount-5),min_note_number(amount-1))
    else:
        return amount

上面还可以优化一下，最小钱币金额是1时，只要金额大于等于第二大金额的钱币就肯定不会只用到1元的。

def min_note_number(amount):
    amount = int(amount)
    if amount <= 0:
        return 0
    if amount == 1:
        return 1
    if amount >= 8:
        return 1 + min(min_note_number(amount-8),min_note_number(amount-5))
    if amount >= 5:
        return 1 + min_note_number(amount-5)
    else:
        return amount