筆試算法模拟題精解之“Tom的手工課”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好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月份比賽正式開啟！機械鍵盤等你拿！