单调数组对的题目 II

单调数组对的题目 II(hard)

做题过程

一开始我想的是用 双指针为基础的优化算法 ，然后感觉不太对，后面绝对可以试试看 多维动态规划（二维） ，又想了一下就没深思，就跳过去了，最后突然觉得回溯应该能写，结果还应该是 多维动态规划 。
总之， 没做出来 。

算法概述

原题

本题要求为给出一个数组，求出由两个非严格递增和非严格递减的数组相加能得到对应索引元素的可能有多少。使用 二维动态规划 。

时间复杂度为O(nm)：n为数组长度，m为最大值
空间复杂度为O(nm)：同上

JAVA

class Solution {
    public int countOfPairs(int[] nums) {
        // 题目还要求将最后的结果对mod这个数求余
        int n = nums.length, m = 0, mod = 1000000007;
        // 找到给出数组中的最大值
        for (int num : nums) {
            m = Math.max(m, num);
        }
        // 一维代表arr1（递增数组）的索引，二维的界限是目标数组中的最大值，这是解法中最妙的点
        int[][] dp = new int[n][m + 1];
        // 因为第一个元素之前没有元素（没有单调性要求），所以可以自由遍历到目标数组中对应索引的值
        for (int a = 0; a <= nums[0]; a++) {
            dp[0][a] = 1;
        }
        for (int i = 1; i < n; i++) {
            // 防止降序排列影响导致d为负数，在循环体内越出边界
            int d = Math.max(0, nums[i] - nums[i - 1]);
            // 这里遍历的是对于当前arr1元素，可能变为的所有值
            for (int j = d; j <= nums[i]; j++) {
                // 小于等于0的范围的只有0
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j-d]; // 就是0 
                } else {
                    // 内部可能数量的前缀和以及外部子问题与子问题之间的继承（迭代）
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % mod;
                }
            }
        }
        int res = 0;
        for (int num : dp[n - 1]) {
            res = (res + num) % mod;
        }
        return res;
    }
}

C++

// 总体思路是一样的

总结

这道题最妙的地方就是把原本一个需要考虑 三个数组相对关系和递增性要求 的复杂问题通过 将二维边界设置为最大值，内层循环每次只考虑当前元素取值的总可能数 的做法构建了子问题结构，从而在利用 动态规划计算前后相对关系 的同时，又 避免了需要向前回溯 的开销。

还需要注意的是：

解法中 只是考虑递增数组 ，外层遍历 只计算前后元素差值 ，不涉及子问题结构
同时int d = Math.max(0, nums[i] - nums[i - 1]);杜绝了因为目标数组降序排列而导致访问空元素的可能

前缀和，迭代（继承），二维动态规划