用 n 根火柴棍能组成多少个非负整数？火柴不必用完，如2根火柴可以组成 1 ，3 根火柴可以组成 1 7 ，4 根火柴可以组成 1, 4, 7, 11
数字 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
需要的火柴数 6, 2, 5, 5, 4, 5, 6, 3, 7, 6
令 d[i] 为用 i 根火柴（全部用上）可以组成的数字个数，则在这些数字之后加上数字 0, 1, ..., 9 得到新数字，即 i 根火柴组成的数字数目 d[i] 可以累计到 i + c[j] 根火柴组成的数字数目 d[i+c[j]] 之内 ( j = 0, ..., 9 c[j] 为组成数字 j 需要的火柴数目)
第一个数字不能为 0 所有 i = 0 时 不能累加到 i + c[0]， 用 小于等于 n 根火柴组成的总数目 f(n) = d(1) + d(2) + .. + d(n)
参考《算法竞赛入门经典训练指南》，刘汝佳，陈锋，P110
// 用 n 根火柴棍能组成多少个非负整数？火柴不必用完，如2根火柴可以组成 1 ，// 3 根火柴可以组成 1 7 ，4 根火柴可以组成 1, 4, 7, 11//// 数字0, 1, 2, 3, 4, 5, 6, 7, 8, 9// 需要的火柴数 6, 2, 5, 5, 4, 5, 6, 3, 7, 6// // 令 d[i] 为用 i 根火柴（全部用上）可以组成的数字个数，则在这些数字之后// 加上数字 0, 1, ..., 9 得到新数字，即 i 根火柴组成的数字数目 d[i] 可以// 累计到 i + c[j] 根火柴组成的数字数目 d[i+c[j]] 之内 ( j = 0, ..., 9 )// c[j] 为组成数字 j 需要的火柴数目//// 第一个数字不能为 0 所有 i = 0 时 不能累加到 i + c[0]//// 用 小于等于 n 根火柴组成的总数目 f(n) = d(1) + d(2) + .. + d(n)//public class StickAndNumber {// 用小于等于 n 根火柴能组成的数字的数目public static int numbersFromStick(int n) {int[] d = new int[n+1];int[] c = { 6,2,5,5,4,5,6,3,7,6 };d[0] = 1;for ( int i=1; i<=n; i++ ) d[i] = 0;for ( int i=0; i<n; i++ ) {for ( int j=0; j<=9; j++) {if ( !(i==0&&j==0) && i+c[j]<=n )d[i+c[j]] += d[i];}}int sum = 0;for ( int i=1; i<=n; i++ ) {sum += d[i];}return (n<6)?sum:(sum+1);}// 测试public static void main(String[] args) {int[] v = { 2, 3, 4 };for ( int x : v ) {System.out.printf("%d:%d%n",x,numbersFromStick(x));}}}
