LC 3250. Find the Count of Monotonic Pairs I

https://leetcode.com/problems/find-the-count-of-monotonic-pairs-i/description/

Tag: DP
Rate: 1897

typedef long long ll;
class Solution {
public:
    int countOfPairs(vector<int>& nums) {
        int n = nums.size();
        ll mod = 1e9 + 7;
        vector<vector<ll>> f(n, vector<ll>(51, 0));
        for (int i = 0; i <= nums[0]; i++) f[0][i] = 1;
        for (int i = 1; i < n; i++) {
            for (int cur = 0; cur <= nums[i]; cur++) {
                int curB = nums[i] - cur;
                for (int pre = 0; pre <= cur; pre++) {
                    int preB = nums[i - 1] - pre;
                    if (curB > preB) continue;
                    f[i][cur] = (f[i][cur] + f[i - 1][pre]) % mod;
                }
            }
        }
        ll ans = 0;
        for (auto &x: f[n - 1]) ans = (ans + x) % mod;
        return ans;
    }
};

就是普通的 DP 而已