1974: A+B+C+D（C语言）动态规划

解题思路:
看到这道题第一反应就是深度优先搜索，提交后超时

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);
    }
}

可以发现这是一道典型的动态规划算法题，

通过观察不难发现动态规划方程为：

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;
}