动态规划 - 矩阵链相乘
一、动态规划的简单介绍
1. 动态规划的定义：
动态规划，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
2. 动态规划的特征：
重叠子问题、最优子结构、无后效性
最优子结构是指一个问题的最优解如果包含其子问题的最优解，则这个问题具有最优子结构。
无后效性的定义是某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。
判断一个问题适不适合用动态规划解决，可以判断问题是不是具有以上3种特征。具有则适合用动态规划方法解决。
3. 解决动态规划问题的步骤：
a. 确定子问题
b.确定状态转移方程
c.确定边界条件
二、矩阵链相乘案例：
1. 题目：
给定n个矩阵序列，(A1,A2,A3,A4,...,An). 计算他们的乘积：A1A2A3...An，求使得乘法次数最小的代价方法
由于矩阵的乘法运算符合结合律，因而可以通过调整计算顺序，从而降低计算量。
示例：
输入p = [5, 10, 3, 12, 5]，即: A1 为 5*10的矩阵，A2为10*3的矩阵， A3为3*12的矩阵，A4为12*5的矩阵，求A1*A2*A3*A4 的最小代价方法。
输出为：最优计算代价：405
最优方案为：((A1A2)(A3A4))
2. 分析：
A1*A2*A3*A4可化为A1~4。
m[i,j]表示Ai一直到Aj相乘的乘法最小次数。
Ai~j可化为Ai~j = Ai~k * Ak~j。其中i<k<j
则m[i,j] = m[i,k]+m[k+1, j]+pi-1*pk+pj
针对示例来说：m[1,4]=m[1, 3]+m[3, 4]+p0*p3*p4=m[1,2]+m[2,4]+p0*p2*p4=m[1,1]+m[1,4]+p0*p1*p4
所以转化为求m[i,j]的问题。
使用前要确定这个问题是不是适合动态规划，即有没有重叠子问题，有没有最优子结构，有没有无后效性质。
a. 有没有重叠子的问题
A1*A2*A3*A4有A1(A2(A3A4))、A1((A2A3)A4))、(A1A2)(A3A4)、A1A2A3A4四种方案
分析过程：
可以看到其中有很多的重叠子。比如 A1*A2，A3A4等等
b. 有没有最优子结构
m[i,j] = m[i,k]+m[k+1, j]+pi-1*pk+pj
m[i,j]的最优解，需要求m[i,k]的最优解和m[k+1, j]的最优解，所以是包含子问题的最优解的
所以具有最优子结构
c. 有没有无后效性
m[i,k]的最优解确定后，无论其他的最优解怎么变化，m[i,k]的最优解是不变的。
综上此问题可以使用动态规划问题解决。
3. 解决步骤：
a. 确定子问题 m[i,j]
b.明确状态，明确选择，确定状态转移方程 m[i,j] = m[i,k]+m[k+1, j]+pi-1*pk+pj
c.确定计算顺序及边界条件 m[i,i] = 0
最优子问题m[i,j]的每一步结果都要存储的话，最适合的存储结构是二维数组。
可以看出，计算顺序最适合的方式是：先求第一条对角线上的解，在求第二条对角线上的解，最后求第三条对角线上的解。因为这样，前边的问题都已经有了计算结果
4. 代码：
'''
matrixChain方法：
设置i为行号，j为列号,n为矩阵个数，目标求m[i，j]
i的取值范围0～n-1，j的取值范围0～n-1
求解顺序，先求第一条对角线上的，在求第二条对角线上的，以此类推，直到最后一条对角线
对角线d的取值范围0～n-1
在每个对角线上，i，j，d之间的关系为 j=i+d
a. 确定对角线d
b. 确定i
c. 确定j
d. 确定k
m 记录的是乘法次数最小的次数
s 记录的是最优解对应的k值
getFun方法：获取最优解的括号位置
同样是一个动态规划问题
s[i,j]记录的是AiAj最优解时k的值
同样以k做为区分点，s[i,k]记录的是AiAk的最优解时对应的k值， s[k+1,j]记录的是Ak+1Aj的最优解时对应的k值
k = s[i-1][j-1]
边界条件，i = j, 意味着就是一个矩阵，故可以直接返回Ai
'''
def matrixChain(p):
num = len(p) - 1
m = [[0] * num for _ in range(num)]
s = [[0] * num for _ in range(num)]
for d in range(1, num):
for i in range(1, num-d+1):
j = i + d
m[i - 1][j - 1] = 9999999999
for k in range(i, j):
template = m[i-1][k-1] + m[k][j-1] + p[i-1]*p[k]*p[j]
if template < m[i-1][j-1]:
m[i-1][j-1] = template
s[i-1][j-1] = k
return m, s
def getFun(s, i, j):
if i == j:
print("A" + str(i), end="")
else:
print("(", end="")
getFun(s, i, int(s[i-1][j-1]))
getFun(s, int(s[i-1][j-1])+1, j)
print(")", end = "")
p = [5, 10, 3, 12, 5]
res, s = matrixChain(p)
print(res)
print(s)
getFun(s, 1, 4)
5. 复杂度
时间复杂度：计算代价的时间：三层循环 O(n^3)
构造最优解的时间：O(n)
总的时间复杂度:O(n^3)
空间复杂度：使用了两个数组，需要空间2*O(n^2)，即O(n^2)