专栏首页算法码上来【每日算法Day 80】所有人都会做的入门题,高级解法来了!

【每日算法Day 80】所有人都会做的入门题,高级解法来了!

题目还是昨天的题,昨天已经介绍了三种解法了,今天介绍一个最快的方法。

题目链接

LeetCode 面试题 08.01. 三步问题[1]

题目描述

三步问题。有个小孩正在上楼梯,楼梯有 阶台阶,小孩一次可以上 阶、 阶或 阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模 。

示例1

输入:
n = 3 
输出:
4
解释:
有四种走法

示例2

输入:
n = 5
输出:
13

题解

昨天的题解地址:

【每日算法Day 79】所有人都会做的入门题,但是能看出你的代码能力!

韦阳的博客:【每日算法Day 79】所有人都会做的入门题,但是能看出你的代码能力![2]

知乎专栏:【每日算法Day 79】所有人都会做的入门题,但是能看出你的代码能力![3]

昨天是通过动态规划来解决的,转移方程为:

初始情况是 。

如果通过递推的方式来求解的话,时间复杂度是 ,但是我们还可以用矩阵快速幂的方法加速到 。

相信大家快速幂一定听说过(没听说过当我没说),如果让你求 ,那么可以分两种情况。如果 是偶数,那么可以计算 ,然后求它的平方 就行了。如果 是奇数,那么可以计算 ,然后求它的平方 就行了。这样只需要用 的复杂度就可以计算出 了。

类似的,如果我们要计算一个矩阵的幂 ,也可以将其拆分成两半,然后计算一半再平方就行了。

那么这题跟矩阵有什么关系呢?如果我们把转移方程右边三项写成向量形式:

那么给它右边乘上一个矩阵 :

那么就会得到向量:

即:

所以乘一次矩阵 就可以得到下一个 值,那么从初始的向量 开始,乘上 就可以得到 了。

而这里的 就可以通过矩阵快速幂来计算得到。

代码

c++

typedef long long ll;
typedef vector<vector<ll>> vvl;
typedef vector<ll> vl;
const ll p = 1e9+7;

class Solution {
public:
    vvl mat_mul(vvl& A, vvl& B) {
        int a = A.size(), b = B.size(), c = B[0].size();
        vvl C(a, vl(c, 0));
        for (int i = 0; i < a; ++i) {
            for (int j = 0; j < c; ++j) {
                for (int k = 0; k < b; ++k) {
                    (C[i][j] += A[i][k] * B[k][j]) %= p;
                }
            }
        }
        return C;
    }

    vvl mat_pow(vvl& A, int n) {
        int m = A.size();
        vvl B(m, vl(m, 0));
        for (int i = 0; i < m; ++i) B[i][i] = 1;
        while (n > 0) {
            if (n&1) B = mat_mul(B, A);
            A = mat_mul(A, A);
            n >>= 1;
        }
        return B;
    }

    vvl mat_pow_rec(vvl& A, int n) {
        if (n == 1) return A;
        vvl B = mat_pow_rec(A, n/2);
        B = mat_mul(B, B);
        if (n&1) return mat_mul(A, B);
        return B;
    }

    int waysToStep(int n) {
        vl f = {1, 2, 4};
        if (n <= 3) return f[n-1];
        vvl A = {{0, 0, 1}, {1, 0, 1}, {0, 1, 1}};
        vvl B = mat_pow(A, n-3);
        ll res = 0;
        for (int i = 0; i < 3; ++i) {
            (res += f[i] * B[i][2]) %= p;
        }
        return res;
    }
};

python

import numpy as np

class Solution:
    def mat_pow(self, A, n):
        m = A.shape[0]
        B = np.eye(m, dtype=np.int64)
        while n > 0:
            if (n&1)!=0:
                B = np.mod(np.matmul(B, A), self.p).astype(np.int64)
            A = np.mod(np.matmul(A, A), self.p).astype(np.int64)
            n >>= 1
        return B;

    def waysToStep(self, n: int) -> int:
        self.p = int(1e9+7)
        f = [1, 2, 4]
        if n <= 3: return f[n-1]
        A = np.array([[0, 0, 1], [1, 0, 1], [0, 1, 1]], dtype=np.int64)
        B = self.mat_pow(A, n-3)
        res = 0
        for i in range(3):
            res += f[i] * B[i][2]
        return int(res%self.p)

参考资料

[1]

LeetCode 面试题 08.01. 三步问题: https://leetcode-cn.com/problems/three-steps-problem-lcci/

[2]

韦阳的博客:【每日算法Day 79】所有人都会做的入门题,但是能看出你的代码能力!: https://godweiyang.com/2020/03/24/leetcode-inteview-08-01/

[3]

知乎专栏:【每日算法Day 79】所有人都会做的入门题,但是能看出你的代码能力!: https://zhuanlan.zhihu.com/p/115799226

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【每日算法Day 99】你们可能不知道只用20万赢到578万是什么概念

    然后从最小的数开始,以它作为顺子的开头,然后看顺子里的数在不在 map 里,在就次数减一,不在就直接返回 false 。

    godweiyang
  • 【每日算法Day 70】图解算法:小学生都会的数块数问题,你会吗?

    在由 1 x 1 方格组成的 N x N 网格 grid 中,每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。

    godweiyang
  • 【每日算法Day 83】邻居小孩一年级就会的乘法表,你会吗?

    给定高度 、宽度 的一张 的乘法表,以及正整数 ,你需要返回表中第 小的数字。

    godweiyang
  • mssql注入

    一些sql扩展 xp_regaddmultistring xp_regdeletekey 删除键名 xp_regdeletevalue 删除键值 xp_...

    赵腰静
  • 关关的刷题日记81 – Leetcode 258. Add Digits

    关关的刷题日记81 – Leetcode 258. Add Digits 题目 Given a non-negative integer num, repeat...

    WZEARW
  • 聊聊spring cloud gateway的SetStatusGatewayFilter

    本文主要研究下spring cloud gateway的SetStatusGatewayFilter

    codecraft
  • C++ 使用 rapidjson 生成 json 并解析

    云胡
  • 聊聊RespCommand

    resp-server-0.16.0/src/main/java/com/github/tonivade/resp/command/RespCommand.ja...

    codecraft
  • 5G时代,华为要做运营商转型的最佳拍档!

    “今年将是5G商用承上启下的关键之年,对运营商未来发展至关重要。”华为中国区运营商Marketing部部长杨涛如是说。

    大数据在线
  • 聊聊RespCommand

    resp-server-0.16.0/src/main/java/com/github/tonivade/resp/command/RespCommand.ja...

    codecraft

扫码关注云+社区

领取腾讯云代金券