当前位置: 首页 > 算法,我的最爱 > 正文

动态规划初学(一) 矩阵连乘与一个最长单调递增串

算法很重要!!!

问题一:

矩阵连乘,相信大家可能熟悉些,不知道的同学请百度。我在这里也装着分析一下。其实挺有意思的。

问题简述:

例如有A1 ,A2, A3, A4, A5,A6 总共6个矩阵,这6个矩阵的乘法顺序不同,则所作的乘法次数总共是不一样的,原因不解释。

解法一:

全排列:搜索出所有的可能组合然后计算出所有答案,总共有2^6个答案,看起来还不是很多,但是如果1000个矩阵可能就比较复杂了,然后保存的空间也受到很大的挑战,所以暴力是不行的,我们需要使用一些更加聪明的办法。

 

解法二:

我们重新分析问题,为了计算出结果,我们必然是需要计算的,并且答案数量还是不少的,所以我们必这是没办法的,搜索这种东西无论如何优化都不可能超过线性的解。

我们发现,其实每一次的答案是和上一次的答案有关系的,如果我们能提前将一些会重复用到的答案都存储起来这样直接就会减少很多很多的运算。对!这就是动态规划的方法。

首先我们寻找其中的递推关系:

i.j 表示第几个矩阵和第几个矩阵相乘。 i * j 表示Ai  * Aj ,数组dp[i][j] 保存其中的值,数组s[i][j]保存结果。

递推关系:

0        ( i == j)   矩阵自乘我们记为0

dp[i][j] =

min{ dp[i][k] + dp[k+1][j] }   + p[i-1]*p[i]*p[j]    i < j

当i < j 的时候,矩阵的复杂程度取决于 它的已知划分 和一个必然的常数项的开销

 

由此我们得出代码,非递归,递归+记忆 大约等与 这个非递归

问题二:

设计一个算法求最长递增子序列。

先来个n^2 的,简单DP.每个DP[i] 记录的是以第i 个下标结尾的最大递增子序列长度。

然后,来一个二分的,这个代码没有测试,先上一个伪代码,后边改

 

 

本文固定链接: http://zmrlinux.com/2016/03/30/%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%e5%88%9d%e5%ad%a6%ef%bc%88%e4%b8%80%ef%bc%89-%e7%9f%a9%e9%98%b5%e8%bf%9e%e4%b9%98%e4%b8%8e%e4%b8%80%e4%b8%aa%e6%9c%80%e9%95%bf%e5%8d%95%e8%b0%83%e9%80%92%e5%a2%9e/ | Kernel & Me

该日志由 root 于2016年03月30日发表在 算法,我的最爱 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 动态规划初学(一) 矩阵连乘与一个最长单调递增串 | Kernel & Me
【上一篇】
【下一篇】