大神的世界

將整數的分割依開頭做分類

因為最大為 200 ，所以共 200 類 （即開頭為 1 ~ 200 ）

另外， 0 的分割還是 0 這邊我們不歸類

要考慮數字 n 有幾種分割方式

只要將數字 n 各類的數量相加即可

例如  n  = 8

8 = 1*   (* 為 7 的任意組合，下面依此類推）

8 = 2*

8 = 3*

8 = 4*

8 = 5*

8 = 6*

8 = 7*

8 = 8*

但這樣可能會導致數字重複，像是 3 + 5  和 5 + 3

因此在考慮分類 3 時，必須規定數字的分割最大只能到 3

程式碼如下

#include <iostream>
#include <stdint.h>

using namespace std;

int main() {

    uint64_t number[201] = {1};

    for(uint32_t i = 1; i <= 200; i++)
        for(uint32_t j = i; j <= 200; j++)
            number[j] += number[j - i];

    int n;
    while(cin >> n)
        cout << number[n] << endl;

    return 0;
}

i = 1

數字    0       1          2                 3

分割     0       10        110             1110

i = 2 

數字    0       1          2                    3

分割     0       10        110   20         1110     210

i = 3

數字    0       1          2                    3

分割     0       10        110   20         1110     210    30

剩下的自己推