有N(1<=N<=50)種不同面值郵票，由這些郵票組成面值1～M，1、2、……、M每種面值均由不超過(guò)K(1<=K<=200)數(shù)目的郵票組成，求最大的M為多少？郵票最大面值為10000

一開(kāi)始想到DP，數(shù)組canComprise[10000*200][200]，canComprise[i][j]表示用j張郵票是否可以組成面值i，但數(shù)組太大，放棄。

后來(lái)改用深搜，優(yōu)化了許久，最后幾組數(shù)組仍然超時(shí)，放棄。

又回頭想DP，如果canComprise[i][j1]和canComprise[i][j2]均為true，j1 < j2，那么canComprise[i][j1]肯定是更優(yōu)的解，因?yàn)閖1可以擴(kuò)展更多i+stamps[x]。所以，只要用一維數(shù)組保存答案就可以了，比如minStamp[i] = j就表示組成i所用到的最少郵票數(shù)為j，遞推式很容易想到：

minStamp[i] = Min{ minStamp[i-stamp[x]] + 1 } ( i – stamp[x] >= 0 )

同一種情況，表達(dá)解的方式可能有多種，盡量使用最精簡(jiǎn)的方式，已達(dá)到降維的效果。