11.28每日一题 前缀和优化DP

题目描述

给你一个长度为 n 的 正 整数数组 nums 。

如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：

两个数组的长度都是 n 。
arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= … <= arr1[n - 1] 。
arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= … >= arr2[n - 1] 。
对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。
请你返回所有 单调 数组对的数目。

由于答案可能很大，请你将它对 109 + 7 取余 后返回。

样例

示例 1：

输入：nums = [2,3,2]

输出：4

解释：

单调数组对包括：

([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2], [1, 1, 0])
示例 2：

输入：nums = [5,5,5,5]

输出：126

徒手分析
先思考最后一个数怎么填 便于翻译成地推
对于 nums【2】=2；

a1 可以0/1/2 a2可以/2/1/0
nums【1】=3
a1 k 可以有哪些？？ 0<=k<=3 k<=2 3-k>=0 所以 0<=k<=2
然后继续递归
就可以写dfs了
需要参数 i 读到那个数了 j当前填的什么 dfs(2,2) 考虑0-2 并且当前填2的情况下有多少单调数对。—dfs(i-1,k)
只需要考虑k的范围 合并可得
nums[i-1]-k>=nums[i]-j (arr2[i])

k≤min(j,nums[i−1]−nums[i]+j)=j+min(nums[i−1]−nums[i],0)

难点是计算k的范围。以及明确可以通过a1a2的限制，减小我们的自由度。

数组题目 可以用填数字的思路思考 比如这个题你要构造一个数组满足什么性质。通过枚举找到一个相似的子问题。 找到必要的参数

第四题 把改成递推之后，用前缀和把最里面的for循环干掉即可。

算法1

(记忆化) $O(nm^2)$

blablabla

时间复杂度=状态个数单个状态的计算时间=Onm Om=Onm^2

参考文献

java 代码

class Solution {
    private int[][] memo;
    private int[] nums;
    private static final int MOD = 1_000_000_007;
    public int countOfPairs(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        memo = new int[n][nums[n - 1] + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);//初始化
        }
        return sumDFS(n - 1, nums[n - 1]) % MOD;
    }

    //表示 考虑下标 0,1,2,3,...,i 时 的单调数组对的数目
    //其中arr1[i] 固定是 j
    private int dfs(int i, int j){
         if (i == 0) {
            return 1;
        }
        if (memo[i][j] != -1) {
            return memo[i][j]; 
        }
        //枚举 arr[i-1] = k 的范围
        //k 的范围
        // 1. 0<= k <= nums[i-1]  
        // 2. arr2[i-1] == nums[i-1] - k  
        // 3. 由第二条件决定 nums[i-1] - k >= arr2[i] == nums[i] - j
        // 4. k <= arr1[i] =j
        //四者表达式化简
        // 0 <= k <= nums[i-1]
        // k <= j
        // k <= nums[i-1] - nums[i] + j
        //决定k的取值范围
        // 0 <= k <= min(nums[i-1], j, nums[i-1] - nums[i] + j)
        int res = 0;
        int maxK = Math.min(nums[i - 1], Math.min(j, nums[i - 1] - nums[i] + j));
        for (int k = 0; k <= maxK; k++) {
            res += dfs(i - 1, k);
            res %= MOD;
        }
        memo[i][j] = res; //记录该数
        return res;
    }

    private int sumDFS(int i, int maxJ){
        int sum = 0;
        for (int j = 0; j <= maxJ; j++) {
            sum += dfs(i, j);
            sum %= MOD;
        }
        return sum;
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla