易错点：火柴也可以组成两位数、三位数等，所以需要一个函数计算数字对应的火柴棒个数。
要使用剪枝
代码：
#include <bits/stdc++.h> using namespace std; const int maxn = 10005; int n, m; int ans = 0; // 记录方案数 int t[4]; int a[10010] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6, 8}; int math1(int r) { // 计算火柴棒个数 if (a[r] > 0) { return a[r]; } else { int an = 0; while (r != 0) { an += a[(r % 10)]; r = r / 10; } return an; } } void dfs(int x, int sum) // 三个位置的第几个位置 { if (sum > n) // 剪枝！！！ return; if (x > 3) { if (t[1] + t[2] == t[3] && sum == n) { ans++; } return; } for (int i = 0; i <= 1000; i++) { t[x] = i; dfs(x + 1, sum + math1(i)); t[x] = 0; } } int main() { scanf("%d", &n); n = n - 4; // 先把n处理了，不然最后一个点会超时 dfs(1, 0); printf("%d", ans); }
或者使用递推进行优化：
代码：
#include <bits/stdc++.h> using namespace std; const int maxn = 10005; int n, m; int ans = 0; // 记录方案数 int t[4]; int a[10010] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6, 8}; void dfs(int x, int sum) // 三个位置的第几个位置 { if (sum > n) // 剪枝！！！ return; if (x > 3) { if (t[1] + t[2] == t[3] && sum == n - 4) { ans++; } return; } for (int i = 0; i <= 1000; i++) { t[x] = i; dfs(x + 1, sum + a[i]); t[x] = 0; } } int main() { scanf("%d", &n); n = n; for (int i = 10; i <= 10000; i++) { // 递推出10~1000所需的火柴棒个数 a[i] = a[i % 10] + a[i / 10]; // 优化！ } dfs(1, 0); printf("%d", ans); }
