Leecode刷题C语言之单调数组对的数目②

执行结果:通过

执行用时和内存消耗如下：

代码如下： 

int countOfPairs(int* nums, int numsSize) {
    int n = numsSize, m = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > m) {
            m = nums[i];
        }
    }
    int mod = 1e9 + 7;
    int **dp = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        dp[i] = (int *)malloc((m + 1) * sizeof(int));
        for (int j = 0; j <= m; j++) {
            dp[i][j] = 0;
        }
    }
    for (int a = 0; a <= nums[0]; a++) {
        dp[0][a] = 1;
    }
    for (int i = 1; i < n; i++) {
        int d = (nums[i] - nums[i - 1]) > 0 ? (nums[i] - nums[i - 1]) : 0;
        for (int j = d; j <= nums[i]; j++) {
            if (j == 0) {
                dp[i][j] = dp[i - 1][j - d];
            } else {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % mod;
            }
        }
    }
    int res = 0;
    for (int j = 0; j <= m; j++) {
        res = (res + dp[n - 1][j]) % mod;
    }
    for (int i = 0; i < n; i++) {
        free(dp[i]);
    }
    free(dp);
    return res;
}

解题思路： 

1. 初始化变量：
   • n：数组 nums 的大小。
   • m：数组 nums 中的最大值，用于确定动态规划数组的第二维大小。
2. 找到数组中的最大值：
   • 遍历数组 nums，找到其中的最大值 m。
3. 动态规划数组的初始化：
   • 创建一个二维数组 dp，其中 dp[i][j] 表示在考虑前 i+1 个元素时，以 j 结尾的满足条件的子序列（或称为“对”）的数量。
   • dp 数组的大小为 n x (m + 1)，因为我们需要考虑所有可能的 nums[i] 值作为结尾。
   • 初始化 dp 数组的所有元素为 0。
4. 基础情况：
   • 对于第一个元素 nums[0]，任何小于等于 nums[0] 的值 j 都可以单独形成一个满足条件的对（即自身与自身配对，虽然题目要求 i < j，但这里是为了初始化方便），因此 dp[0][j] = 1（对于所有 0 <= j <= nums[0]）。
5. 动态规划转移方程：
   • 对于每个元素 nums[i]（i > 0），计算 dp[i][j]：
     • d 是 nums[i] 和 nums[i-1] 的差值（如果 nums[i] 不大于 nums[i-1]，则 d = 0）。
     • 对于每个 j（d <= j <= nums[i]），dp[i][j] 可以由 dp[i-1][j-d] 转移而来（表示在 nums[i-1] 及其之前的元素中，以 j-d 结尾的满足条件的子序列数量）。
     • 特别地，当 j == 0 时，dp[i][0] 只能由 dp[i-1][-d] 转移而来，但由于数组索引不能为负，这里直接设置为 dp[i][0] = dp[i-1][-d]（实际上，由于 d 是基于 nums[i] 和 nums[i-1] 的差值计算的，当 j == 0 时，这个转移逻辑在代码中被特殊处理了，直接复制了 dp[i-1][j-d] 的值，但这里的 j-d 实际上是无效的，因为 j 是从 d 开始的，所以这里的处理是为了代码逻辑上的统一）。
     • 累加 dp[i][j-1] 是因为对于每个 j，dp[i][j] 还包括了所有以 j-1 结尾的满足条件的子序列数量。
6. 结果计算：
   • 遍历 dp[n-1] 的所有元素，累加得到最终结果 res，即所有可能的满足条件的对的数量。
7. 内存释放：
   • 释放动态分配的 dp 数组的内存。
8. 返回结果：
   • 返回计算得到的满足条件的对的数量 res。