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

再举一个长序列的例子说明任务分解，比如1到10:

1 2 3 4 5 6 7 8 9 10
做法和上述一样，最外面的大循环直接for i in range(1，11)从头试到尾，这样把任务分成了两个小任务，即[1,...,i-1]和[i+1,...,10],然后只要我们知道每个小任务的解，那么先猜i的这个大任务的解就是i+max([1,...,i-1],[i+1,...,10])。

比如我们先猜了6

1 2 3 4 5 6 7 8 9 10
任务被分解成1到5和7到10两个小任务，如果我们已经用一个数组存储了这两个小任务的解，那么这个大任务的解直接就是6+max([1,...,5],[7,...,10])
所有1到10都试过之后，再取最小值，得到的就是花费最少的钱数了。即min( 先猜1花的钱 , ... , 先猜10花的钱 )。

最后的问题是怎么构造二维数组存储小任务的解呢，也很简单。这里以1到6举例，太长表格不好画。

1 2 3 4 5 6

表格建立如下，记为T：

1 2 3 4 5 6
1              
2              
3              
4              
5              
6              
行代表任务序列的终点，列代表任务序列的起点(这里行列表示含义互换也一样，只是我自己写代码的时候这么写了懒得改了)。表格中的数代表猜对这个序列至少需要花多少钱。比如T[5][2]就表示从2到5，最少需要花多少钱可以猜对。我们的任务就是填满这个表的下半部分。填满之后，T[6][1]也就是我们要的解。那么我们从头到尾填一遍。
注意:这里我直接从1开始计数便于解释说明，代码的计数是从0开始的。

首先初始化表格为0

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

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

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