第三题只做出来30%,写一下我的思路作为抛砖引玉吧: 首先考虑只由1组成的字符串11111……这个字符串的解释的种类数是一个典型的dp[i] = dp[i -1] + dp[i - 2],即斐波那契数。故如果输入的K是斐波那契数,则我们直接返回一个只有1的字符串即可,1的个数是其在斐波那契数组中的下标。 而对于非斐波那契数,可以尝试拆解成多个斐波那契数之积,比如把4拆成2*2,而中间用只有一种解释的“20”连接起来,这样可以组成112011,有4种解释。
1 6

相关推荐

联想
|
校招
|
超多精选岗位
点赞 评论 收藏
分享
牛客网
牛客企业服务