算法记录：动态规划

1.数位DP#

1.1总体思考#

1.2 题目记录#

1.2.1 LC 3906 统计网格路径中好整数的数目链接 ↗#

对于这个题目，题目要求找[l,r]范围内符合要求的数字个数，而且数据范围很大，[1,9e15],遍历是肯定不可能的，所以需要用数位DP来做。数位DP的核心思想是将问题转化为对数字的每一位进行状态转移，从而避免了暴力枚举所有数字。

同时，对于这种求[l,r]范围内的的答案来说，我们可以把题目转换成求[0,r]范围内的答案减去[0,l-1]范围内的答案。这样就可以通过数位DP来分别计算这两个范围内的符合要求的数字个数，最后得到最终结果。这样在一定的情况下更方便处理。

这题目给的两个限制条件是：

（1）题目给了一个字符串directions，这个字符串就确定了数字的哪些位置是有限制的，对于有限制的位置，要确保当前的限制的位置大于等于上一个被限制的位置的数字，因此要记录上一个被限制的数字，即prev。
（2）同时，对于每一位数字，我们还要记录当前是否已经超过了题目所给的上界r的限制，即isHigh，这样就可以在状态转移时正确地处理边界情况。

然后就是DP，DP就要知道DP数组是是什么样子的，各个维度的含义，以及状态转移方程是怎样的。

使用记忆化搜索（Python可以直接擦车（@Cache）），我们可以定义一个递归函数dfs(i, isHigh, prev)，其中i表示当前处理的数字位，isHigh表示当前是否已经超过了上界r的限制，prev表示上一个被限制的位置的数字。这个函数的返回值就是从当前状态出发，满足条件的数字个数。然后使用一个记忆化数组memo来存储已经计算过的状态，以避免重复计算。

然后我们看转移方程，首先要确定当前位的上界，如果isHigh为true，那么当前位的上界就是s[i]（s是r转换成字符串后的结果），否则当前位的上界就是9。然后对于每个可能的数字d（从0到当前位的上界），我们需要判断是否满足限制条件，如果当前位没有被限制，那么直接递归调用dfs(i + 1, isHigh && (d == upper), prev)；如果当前位被限制，那么需要判断d是否大于等于prev，如果满足条件，则递归调用dfs(i + 1, isHigh && (d == upper), d)。最后将所有满足条件的数字个数累加起来，并存储在memo数组中。

题解代码

class Solution {

    long long dfs(int i, bool isHigh, int prev, const string& s, const vector<int>& pos, vector<vector<vector<long long>>>& memo) {
        if (i == 16) {
            return 1;
        }
        int highFlag = isHigh ? 1 : 0;
        if (memo[i][highFlag][prev] != -1) {
            return memo[i][highFlag][prev];
        }

        long long res = 0;
        int upper = isHigh ? (s[i] - '0') : 9;

        for (int d = 0; d <= upper; ++d) {
            if (pos[i] == -1) {
                res += dfs(i + 1, isHigh && (d == upper), prev, s, pos, memo);
            } else {
                if (d >= prev) {
                    res += dfs(i + 1, isHigh && (d == upper), d, s, pos, memo);
                }
            }
        }
        return memo[i][highFlag][prev] = res;
    }

    long long calc(long long x, const vector<int>& pos) {
        string s = to_string(x);
        if (s.size() < 16) {
            s = string(16 - s.size(), '0') + s;
        }
        vector<vector<vector<long long>>> memo(16, vector<vector<long long>>(2, vector<long long>(10, -1)));
        return dfs(0, true, 0, s, pos, memo);
    }

    long long countGoodIntegersOnPath(long long l, long long r, string directions) {
        vector<int> a;
        a.push_back(0);
        for (char c : directions) {
            if (c == 'D') {
                a.push_back(a.back() + 4);
            } else {
                a.push_back(a.back() + 1);
            }
        }
        vector<int> pos(16, -1);
        for (int i = 0; i < a.size(); ++i) {
            if (a[i] >= 0 && a[i] < 16) {
                pos[a[i]] = i;
            }
        }
        return calc(r, pos) - calc(l - 1, pos);
    }
};

cpp

2.最长递增子序列（LIS）链接 ↗#

2.1总体思考#

最长递增子序列就是一个数组arr中满足下标 $i<j$ 并且 $nums[i]<nums[j]$ 的子序列的最大长度。

只求最大长度

DP方法，其中 $f[i]$ 表示以 $nums[i]$ 结尾的最长递增子序列（LIS）的长度。时间复杂度 $O(n^{2})$

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        for (int i = 0; i < n; i++) {
            f[i] = 0;
            for (int j = 0; j < i; j++) { //从前面找
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i], f[j]);
                }
            }
            f[i]++;//以nums[i]结尾，所以要+1
        }
        return ranges::max(f);
    }
};

cpp

当我们只求最大长度时，存在 $O(nlogn)$ 的算法。这里 $g$ 数组维护的是到遍历的位置为止，当长度为 $g.size()$ 时，最后一个数字最小是多少。在遍历完成之后， $g[i]$ 就是整个数组里面长度为 $i+1$ 的递增子序列的最后一个数字的最小值。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> g;
        for (int x : nums) {
            auto it = ranges::lower_bound(g, x);//求的是严格递增的，然后这里就是使用>=，如果求的是非递减，这里就是>了
            if (it == g.end()) {
                g.push_back(x); // >=x 的 g[j] 不存在
            } else {
                *it = x;
            }
        }
        return g.size();
    }
};

cpp

2.2 题目记录#

2.2.1 LC 3920 删除元素后最大固定点数目链接 ↗#

题目要求在一个数组中删除任意个元素，使得剩下的元素中满足 $nums[i] = i$ 的元素个数最大。那对于选的两个元素下标分别是 $i$ 和 $j$ ，就要保证：

$i < j$ ，因为 $i$ 和 $j$ 都是选的元素的下标，直接假定 $i < j$
$j$ 前面删除的次数要大于等于 $i$ 前面删除的次数，即 $i-nums_i<=j-nums_j$

然后就可以得到二元组 $(nums[i],i-nums[i])$ ，然后这就是二维偏序问题。根据刚刚的两点，也就是这个二元组的第一个元素要递增，第二个元素要单调不降。把按照第一维元素排序后，第一维度的元素就满足了递增的要求了，然后第二维度的元素就要满足单调不降的要求了。然后这个问题就转化成了求第二维度元素的最长非递减子序列的长度了。

这里最长非递减子序列的算法和最长递增子序列的算法是一样的，对于 $O(nlong)$ 的算法中唯一的区别就是在求下标的时候，最长递增子序列是求的是lower_bound，而最长非递减子序列是求的是upper_bound。

题解代码

class Solution {
public:
    int maxFixedPoints(vector<int>& nums) {
        vector<pair<int,int>>arr;
        for(int i=0;i<nums.size();i++){
            int x=nums[i];
            if(i>=x){
                arr.push_back({x,i-x});
            }
            
        }

        sort(arr.begin(),arr.end(),[&](auto &e1,auto &e2){
            if(e1.first==e2.first){
                return e1.second>e2.second;
            }
            return e1.first<e2.first;
        });

        vector<int>g;
        for(auto& [y,h]:arr){
            auto it=ranges::upper_bound(g,h);
            if(it!=g.end()){
                *it=h;
            }
            else{
                g.push_back(h);
            }
        }

        return g.size();
    }
};

cpp

3.最长公共子序列（LCS)链接 ↗#

3.1 总体思考#

最长公共子序列的朴素时间复杂度就是 $O(n^2)$ ,然后 $f[i][j]$ 代表的就是到 $s[i]$ 和 $t[j]$ 为止最长公共子序列的长度。

这里可以从网格图DP的角度去理解，更好理解一些。

class Solution {
public:
    int longestCommonSubsequence(string s, string t) {
        int n = s.size(), m = t.size();
        vector f(n + 1, vector<int>(m + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                f[i + 1][j + 1] = s[i] == t[j] ? f[i][j] + 1 :max(f[i][j + 1], f[i + 1][j]);
            }
        }
        return f[n][m];
    }
};

cpp