求满足A[i]+A[j] =A[k]的最短递增序列的长度？

Question

给定一个正整数P,找出满足如下条件的最短递增序列的长度。

● A[1]=1
● A[n]=P
● 对于任意一个索引k>1,都有i<=j<k满足A[i]+A[j] =A[k]

举例：

输入3，输出3，（因为最短序列为[1,2,3]）

输入16，输出5，（因为最短序列为[1,2,4,8,16]）

输入111，输出10，（因为最短序列为[1,2,3,6,9,18,27,54,57,111]）

Answer 1

不追求效率可以写个bf算法，从1开始求最短递增序列一直求到P