任务终点为5的时候，
任务起点设为5，此时序列为[ 5 ]，不花钱，T[5][5]=0。
任务起点设为4，此时序列为[ 4 , 5],花钱4,则有T[5][4]=4。
任务起点设为3，此时序列为[ 3 , 4 ,5 ],花钱4，则有T[5][3]=4。
任务起点设为2，此时序列为[ 2 , 3 , 4 ,5],有
\[
\begin{array}{l}
T[5][2] \\
=min(2+T[5][3],3+max(T[2][2],T[5][4]),4+max(T[3][2],T[5][5])) \\
=min(2+4,3+4,4+2) \\
=6
\end{array}
\]
任务起点设为1，此时序列为[ 1 , 2 , 3 , 4 , 5 ],有
\[
\begin{array}{l}
T[5][1] \\
=min(1+T[5][2],2+max(T[1][1],T[5][3]),3+max(T[2][1],T[5][4]),4+max(T[3][1],T[5][5]),5+T[4][1]) \\
=min(1+6,2+4,3+4,4+2,5+4) \\
=6
\end{array}
\]
终点为5填写完毕，此时T为
1 2 3 4 5 61 0 0 0 0 0 0
2 1 0 0 0 0 0
3 2 2 0 0 0 0
4 4 3 3 0 0 0
5 6 6 4 4 0 0
6 0 0 0 0 0 0
任务终点为6的时候，
任务起点设为6，此时序列为[ 6 ]，不花钱，T[6][6]=0。
任务起点设为5，此时序列为[ 5 , 6 ]，花钱5，则有T[6][5]=5。
任务起点设为4，此时序列为[ 4 , 5 , 6 ]，花钱5，则有T[6][4]=5。
任务起点设为3，此时序列为[ 3 , 4 , 5 , 6 ]，有
\[
\begin{array}{l}
T[6][3] \\
=min(3+T[6][4],4+max(T[3][3],T[6][5]),5+max(T[4][3],T[6][6]),6+T[5][3]) \\
=min(3+5,4+5,5+3,6+4) \\
=8
\end{array}
\]
任务起点设为2，此时序列为[ 2 , 3 , 4 , 5 , 6 ],有
\[
\begin{array}{l}
T[6][2] \\
=min(2+T[6][3],3+max(T[2][2],T[6][4]),4+max(T[3][2],T[6][5]),5+max(T[4][2],T[6][6]),6+T[5][2]) \\
=min(2+8,3+5,4+5,5+3,6+6) \\
=8
\end{array}
\]
任务起点设为1，此时序列为[ 1 , 2 , 3 , 4 , 5 , 6 ],有
\[
\begin{array}{l}
T[6][1] \\
=min(1+T[6][2],2+max(T[1][1],T[6][3]),3+max(T[2][1],T[6][4]),4+max(T[3][1],T[6][5]),5+max(T[4][1],T[6][6]),6+T[5][1]) \\
=min(1+8,2+8,3+5,4+5,5+4,6+6) \\
=8
\end{array}
\]
终点为6填写完毕，此时整个表格填写完毕。
有T为
1 0 0 0 0 0 0
2 1 0 0 0 0 0
3 2 2 0 0 0 0
4 4 3 3 0 0 0
5 6 6 4 4 0 0
6 8 8 8 5 5 0
到此，T[6][1]=8即为结果。再把上述思路转为代码就搞定了。
代码 class Solution: def getMoneyAmount(self, n): """ :type n: int :rtype: int """ L = [[0]*(n+1) for i in range(n+1)] for i in range(1,n+1): for j in range(1,i)[::-1]: M = n*n if i-j<=2: M = i-1 else: for k in range(j+1,i): M = min(M,k+max(L[k-1][j],L[i][k+1])) L[i][j] = M return L[n][1] 测试结果Runtime:692 ms
beats 69.5% of python3 submissions