375. Guess Number Higher or Lower II (Python) (3)

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

1 2 3 4 5 6
1   0   0   0   0   0   0  
2   1   0   0   0   0   0  
3   0   0   0   0   0   0  
4   0   0   0   0   0   0  
5   0   0   0   0   0   0  
6   0   0   0   0   0   0  

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

1 2 3 4 5 6
1   0   0   0   0   0   0  
2   1   0   0   0   0   0  
3   2   2   0   0   0   0  
4   0   0   0   0   0   0  
5   0   0   0   0   0   0  
6   0   0   0   0   0   0  

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

1 2 3 4 5 6
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   0   0   0   0   0   0  
6   0   0   0   0   0   0  

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwyxwz.html