老师可以帮忙指点指点吗没有什么思路。。

来源：4-6 灵活选择键值 Number of Boomerangs

笨蛋某某某

2019-10-14

给定一个正整数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]）

写回答

1回答

liuyubobobo

2019-10-15

数据规模是怎样的？P最大是多少？

liuyubobobo

笨蛋某某某

我暂时认为只能暴力搜索。对于 1000 以内的数字应该没问题。因为没有数据规模，我也不确定这个问题是否对于更高规模有更好的解。对于很多问题，没有数据规模其实是没有意义的。比如求解哈密尔顿路径，标准的解法就是回溯，即使优化成 dp，依然是指数级别的。数据规模本身是一个问题的重要条件。就算是简单的排序，100个G的数据，也不能再使用普通的归并排序或者快速排序了。

2019-10-15

共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7408 学习 · 1150 问题

查看课程

相似问题

老师，这个解题思路可以吗

回答 2

波波老师，我想打印所有的最短路径，但结果只能输出一条，您能看看是哪里出问题了吗，我定义了一个结构体，记录坐标和当前的路径，队列存储结构体类型。

回答 1

关于leetcode221如何用递归+记忆化搜索方式求解的疑惑，请老师帮忙指点一下

回答 1

leetcode 237题即下图21行，不理解为什么要写node = NULL;node不是被删除了吗，删除意味着什么，难道null还需要保存在节点里吗

回答 1

查找问题的思路

回答 1

打开慕课网App查看更多内容