用矩阵幂求解线性递推序列

用矩阵幂求解线性递推序列
在上一篇文章中我们探讨了如何快速求解幂运算的方法,并且最终给出了一个时间复杂度为O(logn)的算法,那么在这一片文章中,我想说一说快速幂运算的一个应用,也就是利用矩阵的快速幂运算求解线性递推序列。 首先我们来了解下什么是线性递推序列,在这里给大家看一个大家一定很熟悉例子,那就是斐波那契数列,它的递推公式是: 从上面这个方程中我们可以看到很明显的递推关系,实际上我们在做运算的时候,如果一步一步的按照递推式计算,将会消耗大量的时间,于是我们求助于其它的方式。 首先,对于一般的k阶线性递推函数y,应当有这样的形式: 若对于这个递推函数,如果对所有不小于k的n有: 直观来看,这个递推函数应该是长成这个样子的: 当给定了从X(0) ~ X(k – 1) 的k个初始值的时候,我们就能利用这个递推公式计算出所整个序列。那么解决问题的关键就落在了递推函数f的身上。 观察递推函数f的形式,我们发现它可以用两个向量乘积的形式来表达: 为了使用这个函数计算的递推序列能够方便的进入下次的跌打运...

DP最大子段和

动态规划处理“线”上的问题非常在行,今天我们就来探讨求解最大字段和的问题。 问题是这样的。 给定N个整数,要求求出最大的连续子段的和。 例如给定:1 -4 3 1 -2 其最大子段和为:4 该子段为:3 1 我们先来分析这个问题。我们最直观的方法就是穷举所有的子段并求和,找到其中最大的,即为答案,但是明显这样做,效率太低。题目中涉及到了“子段”,这使我们想到动态规划的通过寻找“最优子结构”来找到“最优解”的思路。 给定的N个数字存在数组A[N]当中,然后用B[N]来记录子段和的状态。读者可能有疑问,一个串的子串明显不会只有N个,那为什么只用N个元素来记录状态呢?这样做的原因正是因为我们使用动态规划的思路,B中存储的是状态,串中的每个数字的状态只考虑一次。 那么我们来考虑状态转移方程该如何构造: 假设我们已经得到了一个局部最大子串和B[K-1],考虑算上下一个元素A[K]的时候,这个子串的和为B[K] = B[K – 1] + A[K], 这里算出来B[K]如果大于或等于零,则一定有B[K