数学相关动态规划

algorithm

---

在此输入正文

三角形之和

• 三角形之和
• 题目大意：给定一个三角形数组$triangle$，从上到下构成三角形形状。从上到下能够构成一条路径，路径之和为经过点的值之和，那么问从第一层到最后一层的最小路径之和是多少？

思路1

• 每一条路径都是上一层的某个点转换而成的
• $dp[i][j]$ 表示从定点到$[i,j]$的最短路径，那么$dp[i][j]$，依赖于$dp[i][j-1],dp[i-1][j]$

$$dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j] \\ (i-1,j), (i-1,j-1) \ is\ alid$$
- 初始条件：$dp[i][j] = INT\_MAX$

int minimumTotal(vector<vector<int>>& triangle) {
    int m = triangle.size();
    if(m <= 0 || triangle[0].size() <=0 )
        return 0;
    vector<vector<int>> dp;
    dp.push_back({triangle[0]});
    for(int i = 1; i < m; i++ ) {
        int n = triangle[i].size();
        dp.push_back(vector<int>(n,0));
        for(int j = 0; j < n ; j++){
            dp[i][j] = min(getij(dp,i-1,j-1) , getij(dp,i-1,j)) + triangle[i][j];
        }
    }
    int minv = INT_MAX;
    for(int j = 0; j < triangle[m-1].size();j++) {
        minv = min(dp[m-1][j],minv);
    }
    return minv;
}
int getij(vector<vector<int>> & m , int i ,int j) {
    int n = m.size();
    if(n <= 0 || i < 0 || i >= n || j >= m[i].size() || j < 0 )
        return INT_MAX;
    return m[i][j];
}

• 时间复杂度：$O(n^2)$，空间复杂度：$O(n^2)$
• 从公式$dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]$，能够看出，当前层的计算仅仅依赖于上一层的i结果，所以我们可以用一个数组来表示上一层的结果，一个数组表示当前层的结果，之后交换。进行再下一层的计算。可以把空间复杂度优化到$O(n)$。
• 特别地，这个题，也可以从下往上考虑，题目要求的是从第一行到最后一行，实际上和最后一行到第一行的完全等价的。

---

连续子数组的和为k的倍数

• 连续子数组的和为k的倍数
• 题目大意：给定一个数组${a_0,a_i,\cdots }$，和整数$k$，是否存在一个连续的子数组的和是$k$的$m$倍，$m$ 为整数，且子数组的长度至少为2。

思路1

• 子数组的和为一个数的倍数，那么子数组的和对$k$取余为0。
• 假设对于数组中的数$a_i$，如果这个数和前面的子数组的和构成$k$的倍数，那么可认为存在子数组满足题意。如果$a_i$和前面的子数组的和不构成$k$的倍数，那么可以和前面的子数组构成一个和，这个和的余数和$k$有关系。
• 根据$(a + b) \%k = (a\%k + b \%k )\%k$，我们只需要和前一个数结尾的子数组的和的余数，相加然后在模$k$就能判断是否是$k$的倍数。所以当前的数$a_i$需要和前一个数结尾的子数组和的余数相加，构成$a_i$结尾的子数组和的余数，对前一个数结尾的子数组，我们遍历所有可能的余数与当前数$a_i$相加，对$k$取余，如果有为0的，说明可以构成子数组的和是$k$的倍数。
• 假设$dp[i][j]$表示以$a_i$结尾的数构成的和对$k$的余数为$j$，那么下一个数$a_{i+1}$的状态如何求呢？

$$dp[i][j] = \left\{\begin{matrix} 1 & if \ dp[i-1][t]=1 \&\& j = (a_{i} + t)\%k \\ 0 & else \end{matrix}\right.$$
- 初始情况：$t = a_0 \% k,dp[0][t] = 1$

bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        if(n <= 1 )
            return 0;
        if(k == 0 ) {
            for(int i = 1 ;i < n ;i++) {
                if(nums[i] == 0 &&  (nums[i-1] == 0 )) {
                    return 1;
                }
            }
            return 0;
        }
        k = abs(k);
        vector<vector<int>> dp(n,vector<int>(k,0));
        int idx = nums[0] % k;
        dp[0][idx] = 1;
        for(int i = 1; i < n; i++ ) {
            idx = nums[i] % k;
            for(int j = 0; j < k; j++ ) {
                int t = (j + idx) % k;
                if(dp[i-1][j])
                    dp[i][t] = 1;
            }
            if(dp[i][0])
                return 1;
            dp[i][idx] = 1;
        }
        return 0;
}

• 时间复杂度：$O(n*k)$ ，空间复杂度：$O(n*k)$

思路2

• 由于如果$k$很大，我们需要的空间非常多。实际计算$dp[i][j]$时，只需要知道$dp[i-1][k] != 0$的情况，所以我们可以用map存储上一个状态的余数的情况。例如：$a_{i-1}$的状态中，只有一个数为模是存在的，比如$sum_{i-1}\%k=2$，那么我们用map存储这个模的结果，map[2] = 1，下次计算直接模的结果2与当前数的和，并记录在另一个map中。

bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        if(n <= 1 )
            return 0;
        if(k == 0 ) {
            for(int i = 1 ;i < n ;i++) {
                if(nums[i] == 0 &&  (nums[i-1] == 0 )) {
                    return 1;
                }
            }
            return 0;
        }
        k = abs(k);
        vector<unordered_map<int,int>> dp(n,unordered_map<int,int>());
        int idx = nums[0] % k;
        dp[0][idx] = 1;
        for(int i = 1; i < n; i++ ) {
            for(auto & e : dp[i-1]) {
                idx = nums[i] % k;
                int t = (e.first + idx) % k;
                dp[i][t] = 1;
            }
            if(dp[i].find(0) != dp[i].end())
                return 1;
            dp[i][idx] = 1;
        }
        return 0;
    }

• 时间复杂度：$O(n)$，空间复杂度：$O(n*len(map))$

连续子数组或结果的个数

• 连续子数组或结果的个数
• 题目大意：给定一个非负数组，存在子数组，我们把子数组的所有数据逻辑或运算得到的结果，构成一个集合，问这个集合的大小是多少？
• 与上一题类似，每个子数组的或，为当前数据$a_i$与$a_{i-1}$的数据子数组或结果的逻辑或。
• 用一个全局的map记录所有子数组的或结果，最后返回这个map的大小。
  $$dp[i][j] = \left\{\begin{matrix} 1 & if \ dp[i-1][t] = 1 \&\& j = (a_{i} | t) \\ 0 & else \end{matrix}\right.$$
• 初始情况：$dp[0][a[0]] = 1$

int subarrayBitwiseORs(vector<int>& A) {
        int n = A.size();
        vector<unordered_map<int,int>> dp(n,unordered_map<int,int>());
        unordered_map<int,int> umap;
        dp[0][A[0]] = 1;
        umap[A[0]] = 1;
        for(int i = 1; i< n ;i++) {
            umap[A[i]] = 1;
            for(auto &e : dp[i-1]) {
                int t = e.first | A[i];
                dp[i][t] = 1;
                umap[t] = 1;
            }
            dp[i][A[i]] = 1;
        }
        return umap.size();
}

• 时间复杂度:$O(n*log(mapsize)$，空间复杂度：$O(n*len(mapsize)$
• 由于只使用了相邻数据的结果$a_{i-1}$结尾的子数组或的结果，所以我们保留两个map即可。

---