解题思路:
看到这道题第一反应就是深度优先搜索,提交后超时
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语言代码)浏览:732 |
回文数(一) (C语言代码)浏览:753 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:692 |
校门外的树 (C语言代码)浏览:961 |
A+B for Input-Output Practice (V) (C语言代码)浏览:625 |
WU-小九九 (C++代码)浏览:1684 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:672 |
IP判断 (C语言描述,蓝桥杯)浏览:1095 |
简单的a+b (C语言代码)浏览:546 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:675 |