【在线编程产品介绍】

阿里云开发者社区在线编程：

免费刷题大神器，助你拿到好offer

周赛月赛不停歇，做题还能领奖品

大赛笔试全真题，常做常新有惊喜

点击链接开始产品体验：https://developer.aliyun.com/coding

本文为大家介绍的是“108.Tom的手工课”的解法探究。先来看一下题目内容：

题目详情：

等级：中等
知识点：数学、计数
查看题目：Tom的手工课

一天Tom在上手工课，老师给他们每个人发了一个白色的纸条，上面有n个方格(2<=n<=1e6)。

然后又给他们每个人发了n-1个彩带，一个彩带可以粘到两个相邻的方格上。现在老师让他们把n个方格都粘上彩带(可以不用完n-1个彩带，一个方格上可以重复粘彩带)。

Tom是一个热爱数学的人，他想知道所有的方案中，一共用了多少次彩带(所有的方案所用的彩带的总和)。（答案对1e9+7取模）

输入一个数n表示方格的个数。

输出一个数表示最终方案数，答案对1e9+7取模。

示例1
输入：
3
输出：
4

解题方法：

对于每个方案来说，最少需要n/2个彩带，最多要n-1个彩带，然后我们分别对其进行计算贡献。

操作最多 i 次的方案数是 f[i]，恰好 i 次的方案就是 f[i]−f[i−1]，而 f[i]=C(n-1-I, i-1)。

具体含义:可以看作是每次可以选择 +1,+2 ,求构成 n−2 的方案数,我们先默认都 +1,剩下就是选择 +0,+1 了,只要总共的 i−1 次操作中有 n−1−i 个选择了 +1,就一定可以达到目标了。

看完之后是不是有了答题思路了呢，快来练练手吧：108.Tom的手工课

在线编程周赛、月赛火热进行中，更有限时答题活动，定制卫衣、双肩背包、机械键盘等多重好礼等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程3月份比赛正式开启！机械键盘等你拿！