一个跳格子的题（的变种？）

今天面试的时候被一个超温柔的小哥问了一个超级没头脑的题，小哥最后给了提示但是我……实在是想不出，求各路大神如果知道这个题的原题在哪里或者lc题号求告知！🙏
题目：input是一个array，[2,1,3,4,5]，non negative这样的，每个数字代表当前格子的分值，期待的output为在跳格子的过程中能够拿到的最高分值。
规则如下：如果从idx=0跳到idx=3，在这个example里，获得的分值将为：4*(3-0) = 12。如果从idx=0跳到idx=1，获得的分值为2。规则设定，可以从‘idx=-1’开始跳，即可以从一个out of nowhere的地方跳到某一个格子上，如果直接跳到最后一个格子，这样获得的分值为5*(4-(-1))= 25。如果从-1->2->3->4这样跳，那么就是：3*2+4+5 = 15
我只想到了brute force的方法……从头开始遍历复杂度n^2.....小哥在最后两分钟的样子给我了一个非常vague的方法什么的还祝我能在课余时间想明白……可是我真的不知道应该从何入手sad
求comment求指导！！也求米！！

根据“如果从idx=0跳到idx=3，在这个example里，获得的分值将为：4*(3-0) = 12”  获得的分值是 input[j] * (j - i)

如果从-1->2->3->4这样跳，那么就是：3*（2- -1）+4 *（3-2）+5*（4-3） = 18 而不是15？或者我没理解对？

因此这题的转移应该是

1. for (int j=0 ... N)
   
2.   for (int i=0 ... (j-1))
   
3.     dp[j] = Max(input[j] * (j - i) + input[i])
   

复制代码

DP O(n^2)的复杂度。有无更加优化的方法?

你看这个对不对：假设跳到第i个格子，可以有从-1到i-1个格子跳的选择（总共i个选择），就选其中最大的
dp[i] = max(points[i] * (i + 1),
                    points[i] * i + dp[0],
                    points[i] * (i - 1) + dp[1],
                    ...,
                    points[i] * 1 + dp[i - 1])

不是DP的话 你的复杂度应该是O(2^n)
DP的话也是二维的 O(n^2)
dp[i] = max(dp[i],  nums[i] *  (i - k) + dp[k]), k=0,...i-1



补充内容 (2019-3-9 09:44):
再说一句，这个应该是01背包