矩阵连乘问题（从动态规划超详细解析）

概述

本文将先介绍动态规划，再分析矩阵连乘问题，对动态规划了解的小伙伴可选择性的直接跳到下面。

动态规划

1.概念

动态规划（英语： Dynamic programming，简称 DP） 是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

那动态规划算法要表达的核心思想到底是什么？我们来看一个例子
A : “2+2+2+2+2=? 请问这个等式的值是多少? “
B : “计算 ing 。。。。。。结果为 10 “
A : “那如果在等式左边写上 1+ ，此时等式的值为多少? “
B : “quickly 结果为 11 “
A : “你怎么这么快就知道答案了”
A : “只要在 10 的基础上加 1 就行了 “
A : “所以你不用重新计算因为你记住了第一个等式的值为 10 ,动态规划算法也可以说是’记住求过的解来节省时间‘

由上可知：动态规划算法的核心就是记住已经解决过的子问题的解；而记住求解的方式有两种：

①自顶向下的备忘录法 ②自底向上。

我们先来看一个最简单的例子，我们曾经求解过的斐波拉契数列 Fibonacci。

public int fib(int n){
    if(n <= 1 ){
        return 1;
    }
    if(n == 2){
        return 1;
    }
    return fib(n-1) + fib(n-2);
}

我们分析以前写过的递归就会发现有很多节点被重复执行，如果在执行的时候把执行过的子节点保存起来，后面要用到的时候直接查表调用的话可以节约大量的时间。

2.自顶向下备忘录法

public class Fibonacci {
	public static void main(String[] args) {
		System.out.println(fibonacci(7));
	}
	
	public static int fibonacci(int n) {
		if(n<=0)return -1;//合法性判断
		//创建备忘录
		int[] memo = new int[n+1];
		for(int i=0;i<=n;i++) {
			memo[i]=-1;
		}
		return fib(n, memo);
	}
	/**
	 * 自顶向下备忘录法
	 * @param n
	 * @param memo	备忘录
	 * @return
	 */
	public static int fib(int n,int[] memo) {
		//如果已经求出了 fib（n）的值直接返回
		if(memo[n]!=-1)return memo[n];
		//否则将求出的值保存在 memo 备忘录中。
		if(n<=2)memo[n]=1;
		else {
			memo[n]=fib(n-1, memo)+fib(n-2, memo);
		}
		return memo[n];
	}
}

这个方法是由上至下，比如求f(5),我们要求f(4)和f(3)，求出来后放入备忘录，当求f(4)时需要f(3)和f(2)，我们可以直接从备忘录取f(3)而不是再去求一遍。

3.自底向上的动态规划

备忘录法是利用了递归，上面算法不管怎样，计算 fib（6）的时候最后还是要计算出 fib（1）， fib（2）， fib（3） ……,那么何不先计算出 fib（1）， fib（2）， fib（3） ……,呢？这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。

public class FibonacciPlus {
	/**
	 * 自底向上的动态规划
	 * @param n
	 * @return
	 */
	public static int fib(int n) {
		if(n<=0)return -1;
		//创建备忘录
		int[] memo = new int[n+1];
		memo[0]=0;
		memo[1]=1;
		for(int i=2;i<=n;i++) {
			memo[i]=memo[i-1]+memo[i-2];
		}
		return memo[n];
	}
	/**
	 * 参与循环的只有 i， i-1 , i-2 三项，可以优化空间
	 * @param n
	 * @return
	 */
	public static int fibPlus(int n) {
		if(n<=0)return -1;
		int memo_i_2=0;
		int memo_i_1=1;
		int memo_i=1;
		for(int i=2;i<=n;i++) {
			memo_i = memo_i_1+memo_i_2;
			memo_i_2 = memo_i_1;
			memo_i_1 = memo_i;
		}
		return memo_i;
	}
}

4.钢条切割问题

Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。图15-1给出了一个价格表的样例。

钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。

public class CutSteelBar {
	/**
	 * 递归实现
	 * @param p	钢条长度和价格对应表
	 * @param n	钢条长度
	 * @return
	 */
	public static int cutSteelBar(int[] p,int n) {
		if(n==0)return 0;
		int q = Integer.MIN_VALUE;
		for(int i=1;i<=n;i++) {
			q = Math.max(q, p[i-1]+cutSteelBar(p, n-i));
		}
		return q;
	}
	/**
	 * 自底向上实现
	 * 这里外面的循环是求 r[1],r[2]……，里面的循环是求出 r[1],r[2]……的最优解
	 * 也就是说 r[i]中保存的是钢条长度为 i 时划分的最优解
	 * 一个问题取最优解的时候，它的子问题也一定要取得最优解
	 * @param p
	 * @return
	 */
	public static int buttom2up(int[] p) {
		int[] r = new int[p.length+1];
		for(int i=1;i<=p.length;i++) {
			int q = -1;
			for(int j=1;j<=i;j++) {//这里我们又把问题分为小问题:求出 r[1],r[2]……的最优解
				q = Math.max(q, p[j-1]+r[i-j]);
			}
			r[i]=q;
		}
		return r[p.length];
	}
	
	public static int cutBydemo(int[] p) {
		int[] memo = new int[p.length+1];
		for(int i=0;i<=p.length;i++) {
			memo[i]=-1;
		}
		return cut(p, p.length, memo);
	}
	/**
	 * 自顶向下备忘录法
	 * @param p
	 * @param n
	 * @param memo
	 * @return
	 */
	public static int cut(int[] p,int n,int[] memo) {
		int q = -1;
		if(memo[n]!=-1)return memo[n];
		if(n==0)q=0;
		else {
			for(int i=1;i<=n;i++) {
				q = Math.max(q, cut(p, n-i, memo)+p[i-1]);
			}
		}
		memo[n]=q;
		return q;
	}
}

最优子结构:也就是一个问题取最优解的时候，它的子问题也一定要取得最优解。

问题的最优子结构性质是该问题可用动态规划思想的显著特征。

5.动态规划的适用场景

1. 具有最优子结构性质的问题：指的是问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。
2. 无后效性：无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响，也就是说某状态以后的过程不会影响以前的状态，只与当前状态有关。
3. 具有重叠子问题的问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）；通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。它可以非常显著地降低时间复杂度，提高代码的执行效率。

矩阵连乘问题

1.问题描述

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。例如，给定三个连乘矩阵{A1，A2，A3}的维数分别是10 100，100 5和5 50，采用（A1A2）A3，乘法次数为10100 5+10 5 50=7500次，而采用A1（A2A3），乘法次数为100 5 50+10 100 * 50=75000次乘法，显然，最好的次序是（A1A2)A3，乘法次数为7500次。

加括号的方式对计算量有很大的影响，于是自然地提出矩阵连乘的最优计算次序问题，即对于给定的相继n个矩阵，如何确定矩阵连乘的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

2.问题分析

分析之前我们先来复习一下矩阵乘积的标准算法。

int ra,ca;//矩阵A的行数和列数
int rb,cb;//矩阵B的行数和列数
void matrixMultiply()
{
    for(int i=0;i<ra;i++)
    {
        for(int j=0;j<cb;j++)
        {
            int sun=0;
            for(int k=0;k<=ca;k++)
            {
                sum+=a[i][k]*b[k][j];
            }
            c[i][j]=sum;
        }
    }
}

2.1寻找最优子结构

这个问题的关键特征是：计算A[1:n]的最优次序所包含的矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。

我们可以反证来证明：如果A[1:n]的最优次序所包含的矩阵子链A[1:k]不是最优，那肯定有一个是比他次序少的，我们用其替换A[1:k]，所得的A[1:n]将比先前的更少，也就是说A[1:n]不是最有次序，矛盾

此问题最难的地方在于找到最优子结构。对乘积A1A2…An的任意加括号方法都会将序列在某个地方分成两部分，也就是最后一次乘法计算的地方，我们将这个位置记为k，也就是说首先计算A1…Ak和Ak+1…An，然后再将这两部分的结果相乘。
最优子结构如下：假设A1A2…An的一个最优加括号把乘积在Ak和Ak+1间分开，则前缀子链A1…Ak的加括号方式必定为A1…Ak的一个最优加括号，后缀子链同理。
一开始并不知道k的确切位置，需要遍历所有位置以保证找到合适的k来分割乘积。

2.2建立递归关系

2.3构建辅助表，解决重叠子问题

从第二步的递归式可以发现解的过程中会有很多重叠子问题，辅助表s[n] [n]可以由2种方法构造，一种是自底向上填表构建，该方法要求按照递增的方式逐步填写子问题的解，也就是先计算长度为2的所有矩阵链的解，然后计算长度3的矩阵链，直到长度n；另一种是自顶向下填表的备忘录法，该方法将表的每个元素初始化为某特殊值(本问题中可以将最优乘积代价设置为一极大值)，以表示待计算，在递归的过程中逐个填入遇到的子问题的解。

对于一组矩阵:A1(30x35),A2(35x15),A3(15x5),A4(5x10),A5(10x20),A6(20x25) 个数N为6

那么p数组保存它们的行数和列数：p={30,35,15,5,10,20,25}共有N+1即7个元素

/**
 * 
 * @param p	矩阵链，p[0],p[1]代表第一个矩阵的行数和列数，p[1],p[2]代表第二个矩阵的行数和列数.......
 * @param m	m[i][j]代表从矩阵Ai，Ai+1，Ai+2......直到矩阵Aj最小的相乘次数
 * @param s	s[i][j]记录的是当m[i][j]最小时分割位置k
 * @param n	代表矩阵个数
 */
public static void matrixChain(int[] p,int[][] m,int[][] s,int n) {
    //m[i][i]只有一个矩阵，所以相乘次数为0，即m[i][i]=0;
	for(int i=1;i<=n;i++) {
		m[i][i]=0;
	}
    //l表示矩阵链的长度
	//一个问题取最优解的时候，它的子问题也一定要取得最优解
	for(int l=2;l<=n;l++) {
		for(int i=1;i<=n-l+1;i++) {
			int j=i+l-1;//以i为起始位置，j为长度为l的链的末位
			//默认第一个位置(i)为分割点
			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
			s[i][j]=i;
			//分隔位置k一定在i和j之间
			for(int k=i+1;k<j;k++) {
				int t = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
				if(t<m[i][j]) {
					m[i][j]=t;
					s[i][j]=k;
				}
			}
		}
	}
}

2.4构造最优解

public static void printAnswer(int[][] s,int i,int j) {
	if(i==j) {
		System.out.print("A"+i);
		return;
	}
	System.out.print("(");
	printAnswer(s, i, s[i][j]);
	printAnswer(s, s[i][j]+1, j);
	System.out.print(")");
}

2.5测试代码

public static void main(String[] args) {
    int[] p={30,35,15,5,10,20,25};
    int[][] m = new int[7][7];
    int[][] s = new int[7][7];
    matrixChain(p, m, s, 6);
    printAnswer(s, 1, 6);
}

测试结果：((A1(A2A3))((A4A5)A6))

3.总结

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。

• 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
• 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
• 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
• 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
• 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。

动态规划经典案例

给自己留个坑，日后解决。这里全是问题，没有解答，喜欢挑战的可以试试做一下。

1.线性模型

线性模型的是动态规划中最常用的模型，上面的钢条切割问题就是经典的线性模型，这里的线性指的是状态的排布是呈线性的。我们以一个面试题为例进行说明

面试题：在一个夜黑风高的晚上，有 n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来， i 号小朋友过桥的时间为 T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少？

2.区间模型

区间模型的状态表示一般为 di，表示区间[i, j]上的最优解，然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解，逐步扩大区间的范围，最终求得[1, len]的最优解。
面试题 ：给定一个长度为 n（ n <= 1000）的字符串 A，求插入最少多少个字符使得它变成一个回文串。

3.背包模型

背包问题是动态规划中一个最典型的问题之一，例如：对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？

结语

又有一个伙伴明天开学了，我的孤独又落寞了几分。。。。。。。

最近在想，我要不要魂3死一次学半个小时，感觉可能能学到死😇

这是个休闲游戏，上到九十十九下到刚会走，全都可以得到满意而轻松的游戏体验！请相信我！

赏

谢谢你请我吃糖果

支付宝

微信