当前位置：首页 > news >正文

L25.【LeetCode笔记】三步问题的四种解法(含矩阵精彩解法!)

news 2025/1/4 7:21:33

1.题目

2.三种常规解法

方法1:递归做

编辑

方法2:改用循环做

初写的代码

提交结果

分析

修改后的代码

提交结果

for循环的其他写法

提交结果

方法3:循环+数组

提交结果

3.方法4:矩阵

算法

代码实践

1.先计算矩阵n次方

2.后将矩阵n次方嵌入递推式中

提交结果

1.题目

https://leetcode.cn/problems/three-steps-problem-lcci/

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

示例1:
 输入：n = 3 
 输出：4
 说明: 有四种走法
示例2:
 输入：n = 5
 输出：13
提示:

n范围在[1, 1000000]之间

2.三种常规解法

方法1:递归做

和之前青蛙跳台阶的思想一样(参见35.【C语言】详解函数递归文章),先找递推公式,再写递归

int recursion(int n)
{if (n==1)return 1;if (n==2)return 2;if (n==3)return 4;return (recursion(n-1)+recursion(n-2)+recursion(n-3))%1000000007;
}
int waysToStep(int n) 
{return recursion(n);
}

算法上没问题,但是时间复杂度过高,提交后没有通过

方法2:改用循环做

初写的代码

int waysToStep(int n) 
{if (n==1)return 1;if (n==2)return 2;if (n==3)return 4; int a=1;int b=2;int c=4;int d=0;for (int i=3;i<n;i++){d=a+b+c;a=b;b=c;c=d;}return c%1000000007;
}

提交结果

分析

虽然代码中返回值写成c%1000000007,但是没有完全领会题目的意思,c的值并没有真正改变,可以看看报错的数字:当n==61时,"2082876103 + 1748130326"相加溢出了,可以设想2082876103和1748130326产生的原因,n==某个数溢出了,可以使程序溢出的n的临界值

将代码最后改成return c;测试n的值

多次尝试后

当未模1000000007时,

n==34	n==35	n==34
615693474	1132436852	2082876103

615693474+1132436852=1748130326(大于1000000007),求出了出错提示上的两个数字

a+b+c可能数值超过int的范围,因此要分两次模1000000007,由于d=a+b+c,则程序的计算顺序为:先算a+b,后算+c,则应该对(a+b)先模1000000007再+c,再对d模一次

修改后的代码

        d=(a+b)%1000000007+c;d%=1000000007;a=b;b=c;c=d;

提交结果

for循环的其他写法

for (int i=3;i<n;i++){d=(a+b)%1000000007+c;a=b;b=c;c=d;c%=1000000007;}

提交结果

方法3:循环+数组

int waysToStep(int n) 
{if (n==1)return 1;if (n==2)return 2;if (n==3)return 4;int* arr=(int*)malloc(sizeof(int)*(n+1));arr[1]=1;arr[2]=2;arr[3]=4;for (int i=4;i<=n;i++){arr[i]=(arr[i-3]+arr[i-2])%1000000007+arr[i-1];arr[i]%=1000000007;}return arr[n];}

提交结果

3.方法4:矩阵

算法

$F(n)=F(n-1)+F(n-2)+F(n-3)$

改写成矩阵形式

① $F(n)=\begin{bmatrix} 1 & 1 & 1 \end{bmatrix}\begin{bmatrix} F(n-1)\\ F(n-2)\\ F(n-3)\\ \end{bmatrix}$

② $F(n-1)=\begin{bmatrix} 1 & 0 & 0 \end{bmatrix}\begin{bmatrix} F(n-1)\\ F(n-2)\\ F(n-3)\\ \end{bmatrix}$

③ $F(n-2)=\begin{bmatrix} 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} F(n-1)\\ F(n-2)\\ F(n-3) \end{bmatrix}$

将上方三个式子合三为一

$\begin{bmatrix} F(n)\\ F(n-1)\\ F(n-2) \end{bmatrix}=\begin{bmatrix} 1 & 1 & 1\\ 1 &0 & 0\\ 0 & 1 & 0 \end{bmatrix}\begin{bmatrix} F(n-1)\\ F(n-2)\\ F(n-3) \end{bmatrix}$ (关键式子)

递推

$\begin{bmatrix} F(n-1)\\ F(n-2)\\ F(n-3) \end{bmatrix}=\begin{bmatrix} 1 & 1 & 1\\ 1 &0 & 0\\ 0 & 1 & 0 \end{bmatrix}^2\begin{bmatrix} F(n-2)\\ F(n-3)\\ F(n-4) \end{bmatrix}$

$\begin{bmatrix} F(n-2)\\ F(n-3)\\ F(n-4) \end{bmatrix}=\begin{bmatrix} 1 & 1 & 1\\ 1 &0 & 0\\ 0 & 1 & 0 \end{bmatrix}^3\begin{bmatrix} F(n-3)\\ F(n-4)\\ F(n-5) \end{bmatrix}$ ......

可以一直递推到

**************************************************************************************************************

$\begin{bmatrix} F(n)\\ F(n-1)\\ F(n-2) \end{bmatrix}=\begin{bmatrix} 1 & 1 & 1\\ 1 &0 & 0\\ 0 & 1 & 0 \end{bmatrix}^{n-3}\begin{bmatrix} F(3)\\ F(2)\\ F(1) \end{bmatrix}$

**************************************************************************************************************

设 $\begin{bmatrix} 1& 1 &0 \\ 1& 0 &0 \\ 0& 1&0 \end{bmatrix}^{n-3}=\begin{bmatrix} a & b &c \\ d& e&f\\ g& h & i \end{bmatrix}$ 则最终答案为 $F(n)=a*F(3)+b*F(2)+cF(1)=4a+2b+c$

代码实践

1.先计算矩阵n次方 $\begin{bmatrix} 1& 1 &0 \\ 1& 0 & 0\\ 0&1 & 0 \end{bmatrix}^n$

//矩阵[1,1,1;1,0,0;0,1,0]的n次方(n为计算次数)
#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
int main()
{int arr1[3][3] = { 1,1,1,1,0,0,0,1,0 };int arr2[3][3] = { 0 };int arr3[3][3] = { 1,1,1,1,0,0,0,1,0 };int n;scanf("%d", &n);for (int i = 1; i <= n; i++){if (i % 2)//i为奇数{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){arr2[i][j] = 0;for (int k = 0; k < 3; k++){arr2[i][j] += arr3[i][k] * arr1[k][j];}}}}else{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){arr3[i][j] = 0;for (int k = 0; k < 3; k++){arr3[i][j] += arr2[i][k] * arr1[k][j];}}}}}if (n % 2){for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){printf("%d ", arr2[i][j]);}printf("\n");}}else{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){printf("%d ", arr3[i][j]);}printf("\n");}}return 0;
}

2.后将矩阵n次方嵌入递推式中

int waysToStep(int n) 
{if (n==1)return 1;if (n==2)return 2;if (n==3)return 4;long long  arr1[3][3] = { 1,1,1,1,0,0,0,1,0 };long long  arr2[3][3] = { 0 };long long  arr3[3][3] = { 1,1,1,1,0,0,0,1,0 };n-=4;//不是-3,计算的是矩阵n次方的运行次数for (int i = 1; i <= n; i++){if (i % 2)//i为奇数{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){arr2[i][j] = 0;for (int k = 0; k < 3; k++){arr2[i][j] += (arr3[i][k] * arr1[k][j])%1000000007;}}}}else{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){arr3[i][j] = 0;for (int k = 0; k < 3; k++){arr3[i][j] += (arr2[i][k] * arr1[k][j])%1000000007;}}}}}if (n%2)return (arr2[0][0]*4+arr2[0][1]*2+arr2[0][2])%1000000007;elsereturn (arr3[0][0]*4+arr3[0][1]*2+arr3[0][2])%1000000007;
}

提交结果

封装成函数

其实封装成函数代码看起来更简洁

void calc_matirx_power(long long int (*a)[3] ,long long int (*b)[3] ,long long int (*c)[3] )
{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){a[i][j] = 0;for (int k = 0; k < 3; k++){a[i][j] += (b[i][k] * c[k][j])%1000000007;}}}
}int waysToStep(int n) 
{if (n==1)return 1;if (n==2)return 2;if (n==3)return 4;long long  arr1[3][3] = { 1,1,1,1,0,0,0,1,0 };long long  arr2[3][3] = { 0 };long long  arr3[3][3] = { 1,1,1,1,0,0,0,1,0 };n-=4;//不是-3,计算的是矩阵n次方的运行次数for (int i = 1; i <= n; i++){if (i % 2)//i为奇数{calc_matirx_power(arr2,arr3,arr1);}else{calc_matirx_power(arr3,arr2,arr1);}}if (n%2)return (arr2[0][0]*4+arr2[0][1]*2+arr2[0][2])%1000000007;elsereturn (arr3[0][0]*4+arr3[0][1]*2+arr3[0][2])%1000000007;
}

注意calc_matrix_power参数类型的写法:long long int (*a)[3]

这种写法可以看看这篇文章:★♛★指针（重难点）合集