通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 动态规划精讲(二)矩阵快速幂

161人浏览 / 0人评论 / | 作者:whisper  | 分类: 动态规划  | 标签: leetcode  | 

作者:whisper

链接:https://www.proprogrammar.com/article/1024

声明:请尊重原作者的劳动,如需转载请注明出处


矩阵快速幂是一种基础算法,本身与动态规划没有关系,但它可以用于优化线性递推关系的计算,并且其思路比较固定,因此在计数问题章节之后,在本章将矩阵快速幂做基础介绍。

矩阵快速幂简介


动态规划主要用于解决两类问题,一类是优化问题,求最优解,另一类是组合计数,求方案数。
矩阵快速幂主要用在第二类,即组合计数,求方法数这类问题,可以将时间复杂度从 O(N) 降到 O(logN)。

快速幂

题目

50. Pow(x, n)

快速幂的推导

对以上思路最直接的实现方式是递归, 代码如下:

double _myPow(double x, long long n) 
{
    if (n == 0)
        return 1;
    if (n < 0)
        return 1 / _myPow(x, -n);
    double mid = _myPow(x, n / 2);
    if (n & 1)
        return mid * mid * x;
    return mid * mid;
}

int quickpower(int a, int n)
{
    // a==0 && n==0 特判
    int ans = 1; // n = 0 时候不进循环
    while(n)
    {
        if(n & 1) ans *= a;
        a *= a;
        n >>= 1;
    }
    return ans;
}

矩阵快速幂

矩阵快速幂的推导

以上思路同样可以用二进制分解加位掩码来实现,只是当某个位掩码为 1 表示该位需要的时候,做的是快速幂做的是乘法,矩阵快速幂做的是矩阵乘法。

while(n)
{
    if(n & 1)
        ans = ans * A; // 这一步是矩阵的乘法
    A = A * A;
    n >>= 1;
}

矩阵快速幂的代码模板

实现矩阵快速幂,可以先写一个 struct Matrix 表示矩阵,之后的乘法,求幂都是针对这个类的运算。

其中用一个二维数组做数据成员,一个 init() 方法,将矩阵初始化为单位阵(相当于 A^0 ) 的结果。
然后重载 * 和 ^ 分别表示矩阵乘法和矩阵快速幂。代码如下:

其中 M 表示方阵的行数。

using ll = long long;
const int M = 2;

struct Ma
{
    int a[M][M];
    Ma()
    {
        memset(a, 0, sizeof(a));
    }

    void init() // 复位为单位阵
    {
        a[0][0] = a[1][1] = 1;
        a[0][1] = a[1][1] = 0;
    }

    Ma operator*(const Ma& B) const
    {
        Ma ans;
        for(int i = 0; i < M; ++i)
            for(int j = 0; j < M; ++j)
                for(int k = 0; k < M; ++k)
                    ans.a[i][j] += a[i][k] * B.a[k][j];
        return ans;
    }

    Ma operator^(int n) const
    {
        Ma ans;
        ans.init();
        Ma A = *this; // 拷贝一个出来用于自乘
        while(n)
        {
            if(n & 1)
                ans = ans * A;
            A = A * A;
            n >>= 1;
        }
        return ans;
    }
};

矩阵快速幂的适用问题

矩阵快速幂主要用于线性的递推型计数问题,以及一些动态规划中状态转移方程是线性递推关系的时候。有一些计数问题,通过对 n 比较小的情况进行手动推导,发现规律,可以猜想出递推关系。如果这个递推关系是线性,那么它可以转换成矩阵求幂问题,进而可以用矩阵快速幂加速。

例如斐波那契问题,即力扣第 70 题

题目

70. 爬楼梯

我们会思考是否可以构造一个矩阵 A,使得:

其它的线性递推关系均可以这样做:先找规律得到递推关系,然后将递推关系变为矩阵的形式,套矩阵快速幂。

例如:f(n) = 3f(n - 1) + 6f(n - 2) - 7f(n - 3)f(n)=3f(n−1)+6f(n−2)−7f(n−3),的递推关系,可以变为矩阵形式

在上一章中的 16 道练习题中,部分题目的递推关系是线性的,进而可以用矩阵快速幂来做,尝试判断哪些题目可以用矩阵快速幂做,并用矩阵快速幂解决这些问题,加深对本节的理解。

 


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告