把整數拆分比喻成有 1,2,3,4,5種硬幣
而當我總共有 5元 總共有幾種兌換方法
這邊先說解法，到該硬幣回合時，至少要用1枚該硬幣來換錢，
若真的沒辦法兌換就使用上一次的兌換法（沿用次數）
可以用先前回合兌換過的硬幣來換，若有剩餘，[?] 所對到錢幣兌換方式次數，壘加。
而硬幣的括號表示，該回合可以用的硬幣有哪些
特殊規則：
0表示完全不換成任何硬幣，不把錢找開多少元就多少元，也算成1次
也只有你總金額0元時，可以用0元硬幣兌換。
總金額為1元
1+[0]=1，已兌換1元，剩餘0需要兌換，表達餘額方式 [0]
而[0]這種換法 ，在只能用(0,1)硬幣這回合中 有幾種換法?
從表中左邊查詢 ，查詢到後把上次對換過的方法累加。所以是
(上次有兌換方法數) + (這次可以兌換方法數) = 共有幾種兌換法
0+1 = 1
共1種
總金額為2元
1+[1]=2，已兌換1元，剩餘1需要兌換，表達餘額方式 [1]
而[1]這種換法 ，在只能用(0,1)硬幣這回合中 共有1種
從表中左邊查詢 查詢到後把上次對換過的方法累加 0+1
聰明的你應該發現了可以遞迴累加方式，
當 j 總金額 須對換 i元硬幣時， j 這回合往左 i 格的次數 +上總累積的次數 = 該回合總共可以換的方法
這樣就完成最簡單用快速的整數分拆。
示意圖
| 硬幣＼共有 | 0元 | 1元 | 2元 | 3元 | 4元 | 5元 |
| 0元硬幣 (0) |
共1種換法 | 0 | 0 | 0 | 0 | 0 |
| 1元硬幣 (0,1) |
1 |
1+[0]=1 0+1 = 1 |
1+[1]=2 0+1=1 |
1+[2]=3 0+1=1 |
1+[3]=4 0+1=1 |
1+[4]=5 0+1=1 |
| 2元硬幣 (0,1,2) |
1 | 沒辦法用2硬幣兌換總金額1元，故沿用上次 1 |
2+[0]=2 1+1=2 |
2+[1]=3 1+1=2 |
2+[2]=4 1+2=3 |
2+[3]=5 1+2=3 |
| 3元硬幣 (0,1,2,3) |
1 |
同上 1 |
同上 2 |
3+[0]=3 2+1=3 |
3+[1]=4 3+1=4 |
3+[2]=5 2+3=5 |
| 4元硬幣 (0,1,2,3,4) |
1 |
同上 1 |
同上 2 |
同上 3 |
4+[0]=4 4+1=5 |
4+[1]=3 5+1=6 |
| 5硬幣 可用以下這幾種硬幣 (0,1,2,3,4,5) |
1 |
同上 1 |
同上 2 |
同上 3 |
同上 5 |
5+[0]=5 6+1=7 |
而wiki上的整數拆分，C語言寫的演算法，運算空間更是簡化到用一維陣列就完成
第0回合 初始化換0元硬幣
| 硬幣＼共有 | 0元 | 1元 | 2元 | 3元 | 4元 | 5元 |
| 0元硬幣＼共幾種換法 | 1 | 0 | 0 | 0 | 0 | 0 |
第一回合 換1元硬幣
| 硬幣＼共有 | 0元 | 1元 | 2元 | 3元 | 4元 | 5元 |
| 1元硬幣 | 1 | 1 | 1 | 1 | 1 | 1 |
第二回合 換2元硬幣
1元若不能對換了，就不理他
| 硬幣＼共有 | 0元 | 1元 | 2元 | 3元 | 4元 | 5元 |
| 2元硬幣 | 1 | 1 | 2 | 2 | 3 | 3 |
第三回合 換3元硬幣
1,2元若不能對換了，就不理他
| 硬幣＼共有 | 0元 | 1元 | 2元 | 3 元 | 4元 | 5元 |
| 2元硬幣 | 1 | 1 | 2 | 3 | 4 | 5 |
以此類推
public class PartitionInteger {
public static void main(String[] args) {
solution solution = new solution(); //建立實體
solution.Fun(6); //N參數，共有幾種整數拆分法
}
}
class solution{ //用LEETCODE方式建立類別
void Fun(int len) {
int[] num = new int[len+1];
num[0] =1; //初始化，規則上必要
for(int i=1;i<=len;i++)
for(int j=i;j<=len;j++)
{
//當 j 總金額 須對換 i 元硬幣時， j 這格往左 i 格的次數 +上總累積的次數 = 該回合總共可以換的方法
num[j] +=num[j-i];
}
System.out.println(num[len]);
}
}
本篇文章理解方法源自於下教學。
觀看更多文章請點MRcoding筆記
