打表

打表，是一個信息學專用術語，意指對一些題目，通過打表技巧獲得一個有序表或常量表，來執行程式某一部分，最佳化時間複雜度。這種算法也可用於在對某種題目沒有最優解法時，用來得到分數的一種策略。 打表還可以指計程車開計價器，你要求打表（打開計價器）的話，會顯示出你所經過的里程和所應支付價格，對司機而言就意味著一張發票和費用；所以問你打不打表就是問你要不要發票。如果你和司機是商談了打車的價格，比較便宜的話，一般是不會給你打表的。正常情況下你應該堅持打表，這樣如果有意外事情發生，你可以通過發票追查到你乘坐過的車輛。

打表一般步驟

找到答案的方式

一、通過暴力搜尋，找出對於數據的答案，適用於數據較大，題目簡單的情況；

二、通過手算，找出每個數據的答案，適用於數據較小且題目較難的情況；

三、在某些題目中，因為考慮到預處理出所有答案的時間複雜度可能會比依次讀入再求更優，所以就在讀入數據前進行對所有可能的詢問的答案或部分必要條件的預處理。這種方法雖然也是打表，但編程複雜度不亞於其他程式，而且一般是題目的正解。

輸出答案的方式

一、直接在程式內打表，如果打表複雜度較大則不可用。

二、提前打表，然後複製放入程式。

直接帶入數據的打表占用空間大

打表的技巧

1、可把一些相差不大的數據化為與上一段之差：

例如： f[i]儲存為f[i]-f[i-1]

輸出時以前綴和形式輸出。

2、分段打表。

把數據分為幾段，每段根據輸入數據，找到相應倍數進行輸出。