解题思路:
看到这道题第一反应就是深度优先搜索,提交后超时
void dfs(int target, int pos, int *cnt) { if (pos == 3) { (*cnt)++; return; } for (int i = 1; i < target; i++) { dfs(target - i, pos + 1, cnt); } }
可以发现这是一道典型的动态规划算法题,
0 | 1 | 2 | 3 | 4 | 5 | |
0(A) | 0 | 1 | 1 | 1 | 1 | 1 |
1(B) | 0 | 0 | 1 | 2 | 3 | 4 |
2(C) | 0 | 0 | 0 | 1 | 3 | 6 |
3(D) | 0 | 0 | 0 | 0 | 1 | 4 |
通过观察不难发现动态规划方程为:
dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]
dp[i][j]在这里的含义为,i + 1个数进行组合使得组合后的数字之和为j,这个时候共有dp[i][j]中组合方式。
注意事项:
参考代码:
#include <stdio.h> #define max(a, b) (((a) > (b)) ? (a) : (b)) int main() { int t; scanf("%d", &t); int arr[t]; // 输入数组 int max = 0; // 取到输入数组中最大值,方便确定dp动归数组的的大小 for (int i = 0; i < t; i++) { scanf("%d", &arr[i]); max = max(arr[i], max); } int dp[4][max + 1]; for (int i = 0; i <= max; i++) { dp[0][i] = 1; // 第一行都是1 } for (int i = 0; i < 4; i++) { dp[i][0] = 0; // 第一列都是0 } for (int i = 1; i < 4; i++) { for (int j = 1; j <= max; j++) { dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]; // 动态规划方程 } } for (int i = 0; i < t; i++) { printf("%d\n", dp[3][arr[i]]); // 第i个输入数据进行A+B+C+D时的排列组合 } return 0; }
0.0分
2 人评分
川哥的吩咐 (C++代码)浏览:1010 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:1238 |
淘淘的名单 (C语言代码)浏览:1100 |
WU-小九九 (C++代码)浏览:1684 |
哥德巴赫曾猜测 (C语言代码)浏览:2318 |
蛇行矩阵 (C语言代码)浏览:526 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:560 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:519 |
输出九九乘法表 (C语言代码)浏览:1048 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:591 |