Day 25：动态规划(dynamic programming)

动态规划也是一种演算法设计模式，常用来解决最佳化问题。它的方法是将问题(通常是递回地)分解成子问题，再以子问题的最佳解组成原问题的最佳解。

这样的描述看起来完全就是前面提到的分治法+贪婪演算法，不过动态规划比较特别的一点在於它会储存运算过的子问题解，就可以不用重复运算，也可以将一些运算繁复的问题简化。

因此动态规划适合解决的问题有以下特性：

1. 有最佳子结构(optimal substructure)，也就是可以以子问题最佳解推得原问题最佳解(这部份跟贪婪演算法一样)。
2. 有重叠子问题(overlapping subproblems)，意思是相同的子问题会在运算中反覆出现(最佳组合或组合种类等问题)。

背包问题

举例来说，以贪婪演算法未必会得到最佳解的背包问题(knapsack problem)，就可以以动态规划解决。背包问题是在一组已知重量及价值的物品中，要找出背包可容纳的重量范围内，价值最高的物品组合。

如果以暴力方法解决，就要运算所有的组合，例如当有三样物品A, B, C时，就必须计算A, B, C, A+B, B+C, A+C, A+B+C等所有可能组合，再比较在重量限制内哪一组合的价值最高。这样的方式会反覆运算同样的内容，速度非常慢。

以动态规划解决的话，就会从子问题开始，记录并持续更新最佳解。例如在每样物品最多只能拿一个的情况下，要知道容量三公斤背包装得下的最佳组合，可以记录成类似下面的表格：

从第一列开始，以物品A来说，一、二、三公斤的背包都容纳得下，所以所有容量的当前最佳解都是$500。

第二列，以物品B来说，一公斤背包装不下，最佳解仍为原本的$500；两公斤背包装得下，更新当前最佳解为$1000；三公斤装得下，且装完後还剩下一公斤空间，而我们已记录一公斤的最佳解为$500，所以加起来更新为$1500。

第三列，以物品C来说，一、二公斤的背包都装不下，最佳解维持不变；三公斤背包装得下，但价值并没有超过当前最佳的$1500，所以不更新。

也就是说，动态规划先找出一个物品在各容量背包中的最佳解，并记录下来，接下来如果有别的物品+剩余空间可装物品是更好的组合，就更新记录，而过程中已经计算过的物品不必再次运算。

费氏数列

以费氏数列也可以看动态规划的例子。

费氏数列的开头为0, 1 ，後面的数字都为其前两个数字相加，例如数列的前面几个数字为：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55....

也可以说，除了开头的F0 = 0, F1 = 1之外，数列中的第n个数字Fn，可以写成 Fn = Fn-1 + Fn-2。

如果我们想要写一个函式Fibonacci(n)，在输入n时回传费氏数列中第n个数字(例如Fibonacci(6)回传8)，最简单的作法可以用递回。可以从以下的程序码看到，每一次呼叫Fibonacci(n)，里面会再呼叫Fibonacci(n-1)+Fibonacci(n-2)，两个函式又会再各自呼叫Fibonacci(n-1)+Fibonacci(n-2)...，这样的做法效率很差，而且一直在做一样的计算。

资料来源：Geeksforgeeks

# Function for nth Fibonacci number
 
def Fibonacci(n):
    if n<0:
        print("Incorrect input")
    # First Fibonacci number is 0
    elif n==0:
        return 0
    # Second Fibonacci number is 1
    elif n==1:
        return 1
    else:
        return Fibonacci(n-1)+Fibonacci(n-2)
 
# Driver Program
 
print(Fibonacci(9))
 
#This code is contributed by Saket Modi

如果是动态规划的想法，则是每次将已经算过的数字记录下来，就可以避免上例中的重复计算。例如下方的写法就是将计算过的数字存在阵列中。

# Fibonacci Series using Dynamic Programming
def fibonacci(n):
     
    # Taking 1st two fibonacci numbers as 0 and 1
    f = [0, 1]
     
     
    for i in range(2, n+1):
        f.append(f[i-1] + f[i-2])
    return f[n]
     
print(fibonacci(9))

由上面两个不太一样的问题，可以发现动态规划并非只有一种将问题分解成子问题的方式，有时候需要很多的思考和设计来找到合适的解法。

另外，除了避免重复运算、增进效率外，动态规划会记录子问题解这点，也显示出跟贪婪演算法的一大差异：贪婪演算法是每一步作出当前最佳解，持续把问题缩小，也就不会再回头修改已经作的决定；动态规划则是每一步都是基於前面已得出的子问题解来进行，并可能会更新已得到的答案。