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