这题讲一个叫做根号分治的Tips，以空间换时间最直观的一集。
首先拿到题第一个想到暴力骗分:），考虑我们的搜索算法，发现可以贪心：对于到达一个点xxx，步长为lll，我们只需要知道最多能拿多少个宝石。
因此考虑用BFSBFSBFS+记忆化搜索去做这道题，发现时间复杂度近似为O(N2/d∗log(N2/d))O(N^2 / d *log(N^2/d) )O(N2/d∗log(N2/d))。当d>900的时候，用BFSBFSBFS+记忆化搜索是可以通过此题的。
现在思考这样一个问题：在BFSBFSBFS的过程，我们会遇到很多次点为xxx，步长为lll的状态，这样其实花费了大量的时间。于是窝们考虑设计一个记忆化函数：dp[i][j]dp[i][j]dp[i][j] ， 代表了到达点iii，步长为jjj所能拿到的最多宝石个数。
有了函数后考虑设计状态转移：
dp[i+j+1][j+1]=max(dp[i+j+1][j+1],dp[i][j]+ai+j+1)dp[i + j + 1][j + 1] = max(dp[i + j + 1][j + 1] ,dp[i][j] + a_{i + j + 1})dp[i+j+1][j+1]=max(dp[i+j+1][j+1],dp[i][j]+ai+j+1 )
dp[i+j][j]=max(dp[i+j][j],dp[i][j]+ai+j)dp[i + j][j] = max(dp[i + j][j] ,dp[i][j] + a_{i + j })dp[i+j][j]=max(dp[i+j][j],dp[i][j]+ai+j )
dp[i+j−1][j−1]=max(dp[i+j−1][j−1],dp[i][j]+ai+j−1)dp[i + j - 1][j - 1] = max(dp[i + j - 1][j - 1] ,dp[i][j] + a_{i + j - 1})dp[i+j−1][j−1]=max(dp[i+j−1][j−1],dp[i][j]+ai+j−1 )
这样做的话时间复杂度是O(N2)O(N^2)O(N2)
如果只考虑dpdpdp的话，我们将会把数组开到dp[N][N]dp[N][N]dp[N][N]，这显然是不能够接受的，于是我们就想到了：当ddd足够大的时候，只需要按照BFSBFSBFS+记忆化搜索解决就可以了，这样就可以大大的减少我们的第二维。也就是开头说的：当d>900d>900d>900时考虑暴力、然后通过dpdpdp预处理出d<900d<900d<900的所有答案。这样dpdpdp数组的第二维只需要开到100010001000。时间复杂度为O(N∗1000+N2/1000∗log(N2/1000))O(N*1000 + N^2 / 1000
*log(N^2/1000))O(N∗1000+N2/1000∗log(N2/1000))
（本题的所有d＜100d＜100d＜100）
