Partition(Under Construction!)
使用加法,湊得給定數字
大家都是從數數開始學數學的,1+1=2,想必大家都會。
問題來了!給你一個數,例如5好了,要拿哪些數字相加,才會得到5呢?例如2+3=5、1+1+1+1+1=5等等。
最簡單的方式就是慢慢地列出來,可以發現有許多種相加方式,一時列舉不完。如果你對演算法相當熟悉,你一定馬上聯想到Backtracking、Dynamic Programming等等方法,以及Integer Partition、Knapsack Problem等等問題。
Partition
一個數字的「分割」,是可以用來湊得此數字的所有數字。
湊合與分解,一體兩面。一個數字的「分割」,就是此數字進行分解,可能出現的所有數字。
Young Tableau / Ferrers Diagram
不重覆組合、生成函數
inf sum p(n) xⁿ = 1/(1-x)(1-x²)(1-x³)... Euler n=0
change making / sieve / euler product
https://www.reddit.com/r/algorithms/comments/3dy9ky/
Polygonal Number
http://en.wikipedia.org/wiki/Fermat_polygonal_number_theorem
Tessellation(Under Construction!)
Tessellation
http://en.wikipedia.org/wiki/Tiling_by_regular_polygons
https://www.zhihu.com/question/34916541/answer/60644653
ICPC 3275
Tiling
https://en.wikipedia.org/wiki/Domino_tiling