讨论/题目交流/🐱 第 24 场夜喵双周赛/
🐱 第 24 场夜喵双周赛
展开讨论
力扣 (LeetCode)发起于 2020-04-18
最近编辑于 2020-04-18

罚时太痛了,以后要记住末尾情况和应该用long long的地方。
下午脑袋坑了,思路正确WA了两次不敢继续提交了。
第二题应该是斐波那契那道题是有数学证明的,Zeckendorf's theorem指出任意正整数都可表示为一个或多个不同的斐波那契数之和。所以直接贪心就可以。
这个定理本身用数学归纳法就可以证明。

补充一下证明:
k=1k=1是显然成立.
假设k=1Nk=1…N都成立.
k=N+1k=N+1时,如果kk是斐波那契数,自然成立,否则会有Fibm<k<Fibm+1Fib_{m} < k < Fib_{m+1}.
容易知道0<kFibm<Fibm+1Fibm=Fibm10<k-Fib_m<Fib_{m+1}-Fib_m=Fib_{m-1}.
又因为归纳条件kFibmk-Fib_m可以表示为不同的斐波那契数之和,这些斐波那契数厘米显然不包括FibmFib_m.
所以k=N+1k=N+1也可以表示为不同的斐波那契数之和.
不仅不同,而且还是不连续的斐波那契数之和.

5
展开全部 32 讨论