当前位置: 首页 > article >正文

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

目录

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

提示:

  1. 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==34n==35n==34
61569347411324368522082876103

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;
    else
        return (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;
    else
        return (arr3[0][0]*4+arr3[0][1]*2+arr3[0][2])%1000000007;
}

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

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

提交结果


http://www.kler.cn/a/461568.html

相关文章:

  • Linux实验报告14-Linux内存管理实验
  • Linux驱动开发学习准备(Linux内核源码添加到工程-Workspace)
  • 【51项目】51单片机自制小霸王游戏机
  • 建立一个Macos载入image的实例含界面
  • Singleton: WebRTC中ThreadManager中的单例模式
  • 【Vue3项目实战系列一】—— .eslint.config.js配置文件详细说明,本文除了讲解项目配置项内容,还探讨了更多高级设置并给出参考示例,阅读本文你可以更好地理解和使用 eslint
  • 【高阶数据结构】哈希表
  • 【YOLO算法改进】ALSS-YOLO:无人机热红外图像|野生动物小目标检测
  • 前端网络之【浏览器跨域问题分析与解决方案】
  • 在WPS制作的Excel表格中如何快速插入特殊符号,使用Alt快捷简单又高效
  • 每天40分玩转Django:Django即时聊天应用实战
  • VR线上虚拟展厅有哪些技术支撑?
  • html+css网页制作 美食 美食部落6个页面
  • java AQS
  • cocos creator 3.x版本如何添加打开游戏时首屏加载进度条
  • Qt天气预报系统设计界面布局第三部分
  • 爬虫 - 爬取王者荣耀所有皮肤图片
  • csrf跨站请求伪造(portswigger)无防御措施
  • pyinstaller打包exe可执行文件
  • Cherno C++学习笔记 P47 动态数组Vector
  • JS中的鼠标事件和键盘事件基础
  • 汇川Easy系列正弦信号发生器(ST源代码)
  • Swift Combine 学习(五):Backpressure和 Scheduler
  • 【OpenGL ES】GLSL基础语法
  • AAAI 2025论文分享┆一种接近全监督的无训练文档信息抽取方法:SAIL(文中附代码链接)
  • 【蓝桥杯——物联网设计与开发】基础模块9 - PWM