在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的第69题：正三角塔 的题目解析，具体如下：

题目描述

题目等级：中等
知识点：数学

查看题目：正三角塔 一个正三角形塔，按以下规则叠n层，最高层（第一层）的一个三角形值为1，接下来对于第i层的每个三角形，若是正三角形（尖朝上），则它等于同一层与它相邻的两个三角形值的和（若是没有两个相邻的则值为1）；若是倒三角，则它等于第i-1层与它相邻的一个三角形的值。

问第n层第m个三角形的值为多少（答案对10^9+7取余）？

输入整数n，表示第n层；和整数m，表示第m个三角形（1<=n<=10^5,1<=m<=n*2-1）

输出第n层从左到右第m个三角形的值。

示例1
输入：
3
3
输出：
2

解题思路

这是一个数学问题，将三角塔多写出几层后就可以发现规律。
每一行都是两组组合数，正三角与倒三角分别为一组组合数。
对于第k层，
正三角的值依次为C(k, 1) 到 C(k, k)。
倒三角的值依次为C(k-1, 1) 到C(k-1, k-1)。
根据题中给出的m值，可以判断是正三角还是倒三角，也可以判断是第几个位置。
时间复杂度 与计算组合数的方法有关
空间复杂度 与计算组合数的方法有关

看完之后是不是有了想法了呢，快来练练手吧>>查看题目：正三角塔