动态规划（练习题目）-向日葵屋

故事开始以前  最初的那些春天 阳光洒在杨树上 风吹来 闪银光 街道平静而温暖 钟走得好慢 那是我还不识人生之味的年代
我情窦还不开  你的衬衣如雪 盼着杨树叶落下 眼睛不眨 心里像有一些话  我们先不讲 等待着那将要盛装出场的未来
人随风飘荡  天各自一方 在风尘中遗忘的清白脸庞 此生多勉强 此身越重洋 轻描时光漫长低唱语焉不详 数不清的流年 
似是而非的脸 把你的故事对我讲 就让我笑出泪光 是不是生活太艰难 还是活色生香
我们都遍体鳞伤 也慢慢坏了心肠 你得到你想要的吗 换来的是铁石心肠 可曾还有什么人 再让你幻想 
大风吹来了 我们随风飘荡 在风尘中遗忘的清白脸庞 此生多寒凉 此身越重洋 轻描时光漫长低唱语焉不详
大风吹来了 我们随风飘荡 在风尘中熄灭的清澈目光 我想回头望 把故事从头讲 时光迟暮不返人生已不再来
----------by  朴树 《清白之年》
---------- 2020-02-02

动态规划（Dynamic Programming）：

通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题。

使用动态规划最主要的是要找到状态转移方程，并确定方程的边界条件。

1. 买卖股票的最大收益（只能卖 1 次）

# 保存数组中最小的值
def sellOne(alist):
    minVal, maxProfit = alist[0], 0
    for i in range(1, len(alist)):
        minVal = min(minVal, alist[i])  # 获取数组中的最小值
        maxProfit = max(maxProfit, alist[i] - minVal)
    return maxProfit

2. 买卖股票的最大收益（可以卖无数次）

# 只要今天比前一天的值大时，则卖
def sellInfinite(alist):
    result = 0
    for i in range(1, len(alist)):
        if alist[i-1] < alist[i]:
            result += alist[i] - alist[i-1]
    return result

3. 买卖股票的最大收益（只能卖 2 次）

# 从前到后开始遍历保存收益值，从后到前遍历保存收益值，找到两数组的相加的最大和就是最大的收益
def sellTwo(alist):
    preProfits = [0] * len(alist)  # 第一个值为 0
    postProfits = [0] * len(alist) # 最后一个值为 0
    curMin = alist[0]
    for i in range(1, len(alist)):
        curMin = min(curMin, alist[i])  # 找到前面的最小值
        preProfits[i] = max(preProfits[i-1], alist[i] - curMin)
    curMax = alist[-1]
    for i in range(len(alist)-2, -1, -1):
        curMax = max(curMax, alist[i])  # 找到后面的最大值
        postProfits[i] = max(postProfits[i+1], curMax - alist[i])
    maxProfit = 0
    for i in range(len(alist)):
        maxProfit = max(maxProfit, preProfits[i] + postProfits[i])
    print(preProfits)
    print(postProfits)
    return maxProfit

4.连续数组的最大和

nums = [4, 5, -1, 3, -2, -5, 8, -5]
def getMaxSum(nums):
    d = [0] * len(nums)
    d[0] = nums[0]
    for i in range(1, len(nums)):
        d[i] = max(d[i-1] + nums[i], nums[i])  # 状态转移方程
    return max(d)

5.乘积最大子序列

# 求解一个序列的最大乘积，有0，和负数，正数
# 三种情况的最大值：1. 当前值； 2. 最小值* 当前； 3. 最大值* 当前
def maxProduct(nums):
    d = [[0, 0] for _ in range(len(nums))]
    d[0][0], d[0][1], res = nums[0], nums[0], nums[0]
    for i in range(1, len(nums)):
        t1 = d[i-1][0] * nums[i]   # 保存着最小值
        t2 = d[i-1][1] * nums[i]   # 保存着正数的最大值
        d[i][0] = min(nums[i], t1, t2)
        d[i][1] = max(nums[i], t1, t2)
        res = max(d[i][1], res)
    return res

6.最长递增子序列

# 双层循环， d[i] = {d[j] + 1, where alist[j]< alist[i] and d[i] = {d[j] + 1}
def LIS(alist):
    d = [1] * len(alist)
    for i in range(1, len(alist)):
        for j in range(i):
            if alist[j] < alist[i] and d[i] < d[j] + 1:
                d[i] = d[j] + 1
    return max(d)

7.最长连续递增子序列

def maxContinueSeq(li):
    d = [1] * len(li)
    for i in range(1, len(li)):
        if li[i] > li[i-1]:
            d[i] = d[i-1] + 1
    return max(d)

8.最长公共子序列

# 递推公式为：
# 当num1 == num2时， d[i][j] = d[i-1, j-1] + 1 前几项的LCS 的和
# 当num1 != num2 时，d[i][j] = max{d[i-1, j], d[i, j-1]} 求取最大值 
def LCS():
    s1 = [1, 3, 4, 5, 6, 7, 7, 8] # 公共子序列为： 3,4,6,7,8
    s2 = [3, 5, 7, 4, 8, 6, 7, 8, 2]
    # 创建储存的二维数组, 以s2 的长度 +1 作为列， s1 + 1作为行
    # d = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
    d = np.zeros(shape=(len(s1)+1, len(s2)+1), dtype='int32')
    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            if s1[i-1] == s2[j-1]:
                d[i][j] = d[i-1][j-1] + 1
            else:
                d[i][j] = max(d[i][j-1], d[i-1][j])
    return d[-1][-1]

9.背包问题（类似于LCS）

# 如果 背包容量大于 物品重量：W[i][j] = max(W[i-1][j], W[i-1][j-weights[i-1]] + values[i-1])  W 保存最大的价值
# 如果 背包容量小于 物品重量：W[i][j] = W[i-1][j] 前一背包重量的价值
def knapsack_problem():
    values = [8, 10, 6, 3, 7, 2]
    weights = [4, 6, 2, 2, 5, 1]
    C = 12 # 背包的容量
    # 创建一个二维数组，保存是最大的价值
    # W = [[0]* (C+1) for _ in range(len(weights)+1)]
    w = np.array(shape=(len(weights)+1, C+1), dtype = "int32")
    for i in range(1, len(weights) + 1):
        for j in range(1, C+1): # 包的重量
            if j >= weights[i-1]:
                W[i][j] = max(W[i-1][j], W[i-1][j-weights[i-1]] + values[i-1]) #
            else:
                W[i][j] = W[i-1][j]  # 前一背包重量的价值
    print(np.array(W))
    return W[-1][-1]

10.三角形的最小路径和

# 从倒数第二行开始,往上开始遍历，计算t[i+1][j] 和 t[i+1}[j+1] 的最小值
# 创建一个三角形
triangle = [[1], [4, 6], [7, 3, 5], [2, 3, 10, 12]]
def minPath(triangle):
    height = len(triangle)
    for i in range(height-2, -1, -1):
        for j in range(i+1):
            triangle[i][j] = min(triangle[i+1][j], triangle[i+1][j+1]) + triangle[i][j]
    print(triangle)
    return triangle[0][0]
print(minPath(triangle))

11.零钱兑换

# 两层遍历，外层是钱数，内层是硬币的值， （外层是行，内层是列）
coins = [1, 2, 5]
sum = 11
def coinSums(coins, sum):
    # 确定边界条件
    d = [sum+1] * (sum+1)  # 最多的可能兑换次数是 总值+1 
    d[0] = 0
    for i in range(1, sum+1):
        for coin in coins:
            if i >= coin:
                d[i] = min(d[i], d[i-coin]+1)
    print(d)
    return d[sum]

12.机器人走的路径数

# 当前走的数量等于 左边和上边走的数量
def pathCounts(m, n):
    # m, n 分别表示表格的长和宽
    matrix = [[1] * n for _ in range(m)] 
    # 创建一个长是 m， 宽是 n 的二维矩阵,初始的边界值，当m n==0时，都是1，只有一条路径
    for i in range(1, m): # 先进行行的操作，然后进行列的操作
        for j in range(1, n):
            matrix[i][j] = matrix[i-1][j] + matrix[i][j-1] # 状态转移方程
    return matrix[-1][-1]

13.编辑距离

#  给定两个字符串A和B，要用最少的操作将字符串A转换成字符串B。
d[i-1][j]+1 相当于删除了A 的值
d[i][j-1]+1 相当于插入了A 的值
d[i-1][j-1]  相当于两者替换
def editPath(str1, str2):
    m, n = len(str1), len(str2)
    # d = [[0] * (n+1) for _ in range(m+1)]  # m 是行，n 是列
    d = np.zeros(shape=(m+1, n+1), dtype="int32")
    # 边界条件
    for i in range(1, m+1): d[i][0] = i
    for j in range(1, n+1): d[0][j] = j
    # 状态转移方程
    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:  # 判断两个字符串的值是否相同
                d[i][j] = d[i-1][j-1]
            else:
                d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+1)
    print(d)
    return d[-1][-1]
str1 = "horse"
str2 = "ros"  # 3 次