375. Guess Number Higher or Lower II (Python)

首先初始化表格为0

任务终点为1的时候，此时序列为[ 1 ],不用花钱就能猜对，则有T[1][1]=0。
终点为1填写完毕。此时T没变

任务终点为2的时候，
任务起点先设为2，此时序列为[ 2 ]，不用花钱，则有T[2][2]=0。
下一步任务起点设为1，此时序列为[ 1 , 2 ],花1即可，则有T[2][1]=1。
终点为2填写完毕，此时T为

任务终点为3的时候，
任务起点先设为3，此时序列为[ 3 ],不用花钱，则有T[3][3]=0。
任务起点设为2，此时序列为[ 2 , 3 ],花钱2，则有T[3][2]=2。
任务起点设为1，此时序列为[ 1 , 2 ,3 ],三个的短序列直接可得花钱为中间那个数，也就是2，则有T[3][1]=2。
终点为3填写完毕，此时T为

任务终点为4的时候，
任务起点设为4，此时序列为[ 4 ],不花钱，T[4][4]=0。
任务起点设为3，此时序列为[ 3 , 4 ],花钱3，则有T[4][3]=3。
任务起点设为2，此时序列为[ 2 , 3 , 4 ],花钱3，则有T[4][2]=3。
任务起点设为1，此时序列为[ 1 , 2 , 3 , 4 ]，长度超过3了，要用中长序列的方式去计算。也就是前面举例的方式，有T[4][1]=min(先猜1花的钱,...,先猜4花的钱)
\[ \begin{array}{l} =min(1+[2,3,4] \ , \ 2+max([1],[3,4]) \ , \ 3+max([1,2],[4] \ , \ 4+[1,2,3])) \=min(1+T[4][2] \ , \ 2+max(T[1][1],T[4][3]) \ , \ 3+max(T[2][1],T[4][4]) \ , \ 4+T[3][1]) \=min(1+3 \ , \ 2+3 \ , \ 3+1 \ , \ 4+2) \=4 \end{array} \]
即T[4][1]=4。
终点为4填写完毕，此时T为

终点为5填写完毕，此时T为

任务终点为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为

到此，T[6][1]=8即为结果。再把上述思路转为代码就搞定了。