leetcode 974. Subarray Sums Divisible by K 前缀和+同余定理

题目

https://leetcode.com/problems/subarray-sums-divisible-by-k/
Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

思路

前缀和而后dp同余即可,任意范围的子数组和(i,j] = sum[j]-sum[i],我们要确保他mod K = 0,根据同余定理可知要求 sum[i] mod K == sum[j] mod K 即 sum[i] 同余 sum[j], 所以使用 hashmap 记录余数的个数,后面直接累加

源码

class Solution {
public:
    int sum[30005];
    int res = 0;
    map<int,int> m;
    int subarraysDivByK(vector<int>& A, int K) {
        if(A.size()==0)return res;
        sum[0] = 0;
        m[0] = 1;
        for(int i = 1;i <= A.size();++i){
            sum[i] = sum[i-1]+A[i-1];
            int yu = sum[i]%K;
            if(m.count(yu)==0){
                m[yu] = 1;
            }else{
                m[yu]++;
            }
            res+=(m[yu]-1);
        }
        return res;
    }
};

1498. Number of Subsequences That Satisfy the Given Sum Condition 区间最大最小

题目

https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/submissions/
Given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal than target.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)
Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don’t satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 – 2 = 61).
Example 4:

Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 – 1) = 127

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= target <= 10^6

思路

首先对数组进行排序
遍历以各元素开始的子序列,针对起始元素例如3,target为9时要求max最大为6,则找到最后一个小于等于6的位置,计算该长度内以3开头的子序列数量。
我们知道大小为3的数组的子集为 2^3-1,其中以第一个元素开头的子序列数量为 2^2,原理为第一位确定后,第二位可以要可以不要2种选择,第三位同理
注意 不要写r+=a%b,写 r = (r+a)%b

源码

class Solution {
public:
    long long res = 0;
    int pows[100005]={0};
    int numSubseq(vector<int>& nums, int k) {
        vector<int> re;
        sort(nums.begin(),nums.end());
        re = nums;
        reverse(re.begin(),re.end());

        pow2();
        for(int i = 0;i < nums.size();++i){
            if(nums[i] > k)break;
            int bd = k - nums[i];
            auto idx = lower_bound(re.begin(),re.end()-i,bd,greater<int>());   
            int len = (re.end()-idx)-i;
            cout <<len<<endl;
            if(len!=0)
            res = (res+pows[len-1])%(int)(1e9+7);
           // cout<<res<<endl;
        }
        return res;
    }
    void pow2(){
        pows[0]=1;
        for(int i = 1;i <= 1e5;++i){
            pows[i] = (2*pows[i-1])%(int)(1e9+7);
           // cout <<pows[i]<<endl;
        }
    }
};

1520. Maximum Number of Non-Overlapping Substrings Hard 可转化为01背包

题目

https://leetcode.com/contest/weekly-contest-198/problems/maximum-number-of-non-overlapping-substrings/
Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that meet the following conditions:

The substrings do not overlap, that is for any two substrings s[i..j] and s[k..l], either j < k or i > l is true.
A substring that contains a certain character c must also contain all occurrences of c.
Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.

Notice that you can return the substrings in any order.

Example 1:

Input: s = “adefaddaccc”
Output: [“e”,”f”,”ccc”]
Explanation: The following are all the possible substrings that meet the conditions:
[
“adefaddaccc”
“adefadda”,
“ef”,
“e”,
“f”,
“ccc”,
]
If we choose the first string, we cannot choose anything else and we’d get only 1. If we choose “adefadda”, we are left with “ccc” which is the only one that doesn’t overlap, thus obtaining 2 substrings. Notice also, that it’s not optimal to choose “ef” since it can be split into two. Therefore, the optimal way is to choose [“e”,”f”,”ccc”] which gives us 3 substrings. No other solution of the same number of substrings exist.
Example 2:

Input: s = “abbaccd”
Output: [“d”,”bb”,”cc”]
Explanation: Notice that while the set of substrings [“d”,”abba”,”cc”] also has length 3, it’s considered incorrect since it has larger total length.

Constraints:

1 <= s.length <= 10^5
s contains only lowercase English letters.

思路

这题分为两部分,第一部分要找到合法的字串

  1. 找到所有字母的最小下标和最大下标
  2. 针对每一个字母将游标从其最小下标开始遍历,针对每一个字母判断如果无法包含在当前区间内,则该字母无法作为一个合法字符串的开头;否则更新 end 的值,该方法是贪心的得到的都是最短的合法字串

第二部分为01背包问题,再取得最大价值的同时还要保证最小容量
其中dp可以保证最小容量,要注意的是非状态压缩的数组不能所见遍历范围,会导致部分值无法被继承,比如 j 从 0 开始不能仅仅遍历到 start

源码

class Solution {
public:
    static bool cmp(vector<int> a,vector<int> b){
        return a[0] > b[0];
    }
    vector<string> maxNumOfSubstrings(string s) {
        vector<vector<int>> bg(26),valid;
        for(int i = 0;i < s.length();++i){
            bg[s[i]-'a'].push_back(i);
        }
        for(int i = 0;i < 26;++i){
            if(bg[i].size() < 1) continue;
            int end = bg[i].back();
            int idx = bg[i][0];
            bool f = true;
            for(;idx!=end;idx++){
                //cout << idx<<endl;
                if(s[idx]=='a'+i)continue;
                if(bg[s[idx]-'a'][0]<bg[i][0]){
                    f = false;
                    break;
                }
                end = max(end,bg[s[idx]-'a'].back());
            }
            //合法
            if(f){
                vector<int> pair;
                pair.push_back(bg[i][0]);
                pair.push_back(end);
                valid.push_back(pair);
            }
        }
        //输出合法字符串长度
        sort(valid.begin(),valid.end(),cmp);
        //背包问题
        vector<long> dp(s.length()+1,0);
        vector<vector<int>> path(valid.size()+1,vector<int>(s.length()+1,0)),se(valid.size()+1,vector<int>(s.length()+1,0));
        for(int i = 0;i < valid.size();++i){
            //cout <<"i = "<<i<<endl;
            int len = valid[i].back()-valid[i][0]+1;
            int start = valid[i][0];
            int end = valid[i].back();
            //cout <<"Start = "<<start<<endl;
            for(int j = 0;j <= s.length();++j){
                if(j>start){
                    path[i][j]=i==0?0:path[i-1][j];
                    continue;
                }
                if(dp[j]>dp[end+1]+1){
                    //不选
                    dp[j] = dp[j];
                    path[i][j] = i==0?0:path[i-1][j];
                    se[i][j]=0;
                }else if(dp[j]<dp[end+1]+1){
                    //选
                    dp[j] = dp[end+1]+1;
                    path[i][j] = i==0?len:path[i-1][end+1]+len;
                    se[i][j]=1;
                }else{
                    if(path[i-1][j]<path[i-1][end+1]+len){
                        //不选
                        dp[j] = dp[j];
                        path[i][j] = i==0?0:path[i-1][j];
                    }else{
                        //选
                        dp[j] = dp[end+1]+1;
                        path[i][j] = i==0?len:path[i-1][end+1]+len;
                        se[i][j]=1;
                    }
                }
               // dp[j] = max(dp[j],dp[end+1]+1);
                //cout <<"path"<<j<<" = "<<path[i][j]<<endl;
            }
           // cout<<endl;
        }
        //cout << dp[0]<<endl;
        int idx = 0;
        vector<string> res;
        for(int i = valid.size()-1;i >=0;--i){
            int len = valid[i].back()-valid[i][0]+1;
            if(se[i][idx]!=0){
                string  ss = s.substr(valid[i][0],len);
                idx+=len;
               // cout << ss<<endl;
                res.push_back(ss);
            }
        }
        return res;
    }
};

leetcode 1530. Number of Good Leaf Nodes Pairs LCA 最近公共祖先

题目

https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/
Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.
Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.
Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].
Example 4:

Input: root = [100], distance = 1
Output: 0
Example 5:

Input: root = [1,1,1], distance = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 2^10].
Each node’s value is between [1, 100].
1 <= distance <= 10

思路

对于dfs分别计算两个子树中的叶子对数,然后再求叶子分别处于两个子树中的对数。
对于每颗子树返回其中的对数,和每层叶子节点的数量,即只记录叶子节点所在层数,不记录dfs路径长度,而后两个叶子节点的距离即为深度和
这样可以避免重复,左右子树中的叶子节点都以当前节点为 LCA ,最近公共祖先

源码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
struct RES{
    int cnt = 0;
    vector<pair<int,int>> dis;
};
class Solution {
public:
    int dd;
    int countPairs(TreeNode* root, int distance) {
        dd = distance;
       RES res =  dfs(root);
        return res.cnt;
    }
    RES dfs(TreeNode* root){
        RES res;
        if(root == NULL)return res;
        if(root->left==NULL&&root->right==NULL)
            res.dis.push_back(make_pair(0,1));
        RES l = dfs(root->left);
        RES r = dfs(root->right);
        res.cnt = l.cnt+r.cnt;
        for(int i = 0;i < l.dis.size();++i){
            for(int j = 0;j < r.dis.size();++j){
                pair<int,int> ll = l.dis[i];
                pair<int,int> rr = r.dis[j];
               // cout << ll.first<<" "<<rr.first<<" d: "<<ll.second<<" "<<rr.second<<endl;
                if(ll.first+rr.first+2<=dd){
                    res.cnt+=ll.second*rr.second;
                }
            }
        }
      //  cout << l.cnt<<endl;
        //cout << r.cnt<<endl<<endl;
        map<int,int> m;
        for(auto p:l.dis){
            m[p.first]+=p.second;
        }
        for(auto p:r.dis){
            m[p.first]+=p.second;
        }
        for(auto p:m){
            res.dis.push_back(make_pair(p.first+1,p.second));
        }
        return res;
    }
};

discuss 里看见一份代码同样的逻辑后续遍历,人家代码写的就贼优雅

/*
    https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/submissions/

    Idea is to find out the distance of leaf nodes in left and right subtrees
    for each of the parent nodes. For a node 'i', if we know the distance of leaf nodes
    in its left and right from it, then we can just check if the sum of distance of the leaf nodes
    in left and right <= dist limit, that makes it a good pair.

*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // TC: O(n * d * d), d: max distance limit, n: num of nodes
    vector<int> postOrder(TreeNode *root, int &distance,
                          int &good_leaves) {
        // dist(i): no. of leaf nodes with dist 'i' from current node
        vector<int> dist(distance + 1, 0);
        if(!root)
            return dist;

        // when current is a leaf node, its distance with its parent will be 1
        if(!root->left && !root->right) {
            dist[1] = 1;
            return dist;
        }

        // find the distance of leaf and right subtree leaf nodes
        auto left_dist = postOrder(root->left, distance, good_leaves);
        auto right_dist = postOrder(root->right, distance, good_leaves);

        // now check the distances between leaf nodes of leaf and right 
        // subtrees which are under limit
        for(int i = 0; i < left_dist.size(); i++)
            for(int j = 0; j < right_dist.size(); j++)
                if(i + j <= distance) {
                    good_leaves += (left_dist[i] * right_dist[j]);
                }
        // Update the distance for parent and include the current node
        for(int i = 1; i <= distance; i++) {
            // (i-1) distance becomes distance 'i' 
            dist[i] = left_dist[i-1] + right_dist[i-1];
        }

        return dist;
    }


    int countPairs(TreeNode* root, int distance) {
        int good_leaves = 0, curr_dist = -1;
        postOrder(root, distance, good_leaves);
        return good_leaves;
    }
};

leetcode 1537. Get the Maximum Score merge 变体 取模谨慎

题目

https://leetcode.com/contest/weekly-contest-200/problems/get-the-maximum-score/
You are given two sorted arrays of distinct integers nums1 and nums2.

A valid path is defined as follows:

Choose array nums1 or nums2 to traverse (from index-0).
Traverse the current array from left to right.
If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).
Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10], (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10] (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].
Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].
Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].
Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61

Constraints:

1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 and nums2 are strictly increasing.

思路

merge sort
i,j 分别为两个 list 的游标,向前移动并累计求和,对于相同值的两个节点,其后可以选择之前的任意一个分支,同一个 list 两个跳转节点间的值可以压缩为一个节点,所以最终将跳转节点位置对齐,便利跳转节点只需要选择两个 list 中值较大的即可
注意取模的坑,取模会影响 max 操作,所以建议使用 longlong,将取模操作放到最后

源码

class Solution {
public:
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        int  i = 0,j = 0;
        int mod = 1000000007;
        long long res = 0;
        long long sum1 = 0,sum2 = 0;
        while(i<nums1.size()&&j<nums2.size()){
            if(nums1[i]==nums2[j]){
                res = (res+max(sum1,sum2)+nums1[i])%mod;
                sum1 = sum2 = 0;
                i++;
                j++;
            }else if(nums1[i]<nums2[j]){
                sum1=(sum1+nums1[i]);
                i++;
            }else{
                sum2=(sum2+nums2[j]);
                j++;
            }
        }
        while(i!=nums1.size()){
            sum1=sum1+nums1[i];
            i++;
        }
        while(j!=nums2.size()){
            sum2=sum2+nums2[j];
            j++;
        }
        return res=(res+max(sum1,sum2))%mod;
    }
};

leetcode 1536. Minimum Swaps to Arrange a Binary Grid 贪心冒泡排序

题目

https://leetcode.com/contest/weekly-contest-200/problems/minimum-swaps-to-arrange-a-binary-grid/
Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.

A grid is said to be valid if all the cells above the main diagonal are zeros.

Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.

The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).

Example 1:

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3
Example 2:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
Explanation: All rows are similar, swaps have no effect on the grid.
Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,1]]
Output: 0

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 200
grid[i][j] is 0 or 1

思路

排序问题,把行数据转换为右边连续的0的个数,而后进行冒泡排序,但是改为贪心策略,对应位置需要的数为 n,n-1,n-2…3,2,1,0 从最高位开始如果该位置的数>=对应的要求,则跳过,如果小于,则向后寻找第一个满足该目标的数,冒泡交换到该位置,记录交换次数,如果找不到则返回-1
基于这样一个思想

当前位置所需要的数一定是最大的,所以向后寻找时第一个满足的数即使是剩余目标中的最大数也是符合预期的,而最近保证了交换次数最小

源码

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        vector<int> nums;
        for(auto p:grid){
            int count = 0;
            for(int i = p.size()-1;i>=0;--i){
                if(p[i]==0){
                    count++;
                }else break;
            }
            nums.push_back(count);
        }
        int res = 0;
        for(int i = 0;i < nums.size();++i){
            if(nums[i] < nums.size()-i-1){
                bool f = true;
                for(int j = i+1;j < nums.size();++j){
                    if(nums[j]>=nums.size()-i-1){
                        int t = nums[j];
                        nums.erase(nums.begin()+j);
                        nums.insert(nums.begin()+i,t);
                        res += j-i;
                        f = false;
                        break;
                    }
                }
                if(f)return -1;
            }
        }
        return res;
    }
};

leetcode 1547. Minimum Cost to Cut a Stick 区间dp

题目

https://leetcode.com/problems/minimum-cost-to-cut-a-stick/
Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:

Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.

You should perform the cuts in order, you can change the order of the cuts as you wish.

The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.

Return the minimum total cost of the cuts.

Example 1:

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:

The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).
Example 2:

Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering the cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.

Constraints:

2 <= n <= 10^6
1 <= cuts.length <= min(n – 1, 100)
1 <= cuts[i] <= n – 1
All the integers in cuts array are distinct.

思路

1000 题合并石堆还简单,是 K = 2 的特殊情况,直接区间 dp AC,参考矩阵乘法结合律优化
cuts 数组直接作为向前累加和,注意排序

源码

class Solution {
public:;
    ;
    int minCost(int n, vector<int>& cuts) {
        cuts.push_back(n);
        sort(begin(cuts),end(cuts));
        vector<vector<int>> dp(cuts.size()+1,vector<int>(cuts.size()+1,INT_MAX));  
        return calDp(0,cuts.size()-1,cuts,dp);
    }
    int calDp(int i,int j,vector<int>& cuts,vector<vector<int>>&dp){
        if(dp[i][j] != INT_MAX){
            return dp[i][j];
        }
        if(i == j){
           return dp[i][j] = 0;
        }else if(i+1 == j){
           return dp[i][j] = cuts[j]-(i==0?0:cuts[i-1]);
        }else{
            for(int k = i;k < j;++k){
                dp[i][j]=min(dp[i][j],calDp(i,k,cuts,dp)+calDp(k+1,j,cuts,dp)+cuts[j]-(i==0?0:cuts[i-1]));
            }
        }
        return dp[i][j];
    }
};

leetcode 1000. Minimum Cost to Merge Stones 区间dp 归并

题目

https://leetcode.com/problems/minimum-cost-to-merge-stones/
There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.

A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.

Find the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Example 1:

Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation:
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.
Example 2:

Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can’t merge anymore. So the task is impossible.
Example 3:

Input: stones = [3,5,1,2,6], K = 3
Output: 25
Explanation:
We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.

Note:

1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

思路

区间 dp
子问题划分要把 [i,j] 范围内的石堆合并成 k 个石堆,需要考虑从 t 开始,[i,t] 合并成一个石堆,[t+1,j] 合并成 k-1 个石堆,t 的步长为 K-1,边界条件为 i == j

源码

class Solution {
public:
    vector<vector<vector<long>>> dp;
    vector<int> pre;
    int DK;
    int mergeStones(vector<int>& stones, int K) {
        DK = K;
        dp.resize(stones.size()+1,vector<vector<long>>(stones.size()+1,vector<long>(K+1,INT_MAX)));
        pre.resize(stones.size()+1,0);
        for(int i = 0;i < stones.size();++i){
            pre[i]=pre[i==0?0:i-1]+stones[i];
        }
        return calDp(0,stones.size()-1,1)==INT_MAX?-1:calDp(0,stones.size()-1,1);
    }
    long calDp(int st,int ed,int k){
        if(dp[st][ed][k]!=INT_MAX)return dp[st][ed][k];
        if(st==ed){
            return dp[st][ed][k] = k==1?0:INT_MAX;
        }
        if((ed-st-k+1)%(DK-1)!=0){
            return dp[st][ed][k] = INT_MAX;
        }
        if(k == 1){
            return dp[st][ed][1] = calDp(st,ed,DK)+pre[ed]-(st==0?0:pre[st-1]);
        }
        for(int t = st;t < ed;t += (DK-1)){
            dp[st][ed][k] = min(dp[st][ed][k],calDp(st,t,1)+calDp(t+1,ed,k-1));
        }
        return dp[st][ed][k];
    }
};

leetcode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target 动态规划 向前累积和

题目

https://leetcode.com/contest/weekly-contest-201/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/
Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).
Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.
Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3
Example 4:

Input: nums = [0,0,0], target = 0
Output: 3

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6

思路

记录累计和,同时每次只需要找 s[i] – target 的位置,然后max(dp+1,dp),即分别对应是否选择第 i 位,其中寻找 s[i]-target 时,从后向前找,第一个命中即可,因为dp[i+1]>=dp[i],即数组越长,则值一定越大,所以贪心保证选择i后的子序列最短即可。
为了提高效率,使用map记录,其中为了避免保证找到的索引一定小于i,在更新dp后再更新map

源码

class Solution {
public:
    vector<int> dp,s;
    map<int,int> m;
    int maxNonOverlapping(vector<int>& nums, int target) {
        dp.resize(nums.size()+1,0);
        s.resize(nums.size()+1,0);
        int sum = 0;

        for(int i = 0;i<nums.size();++i){
            sum+=nums[i];
            s[i]=sum;

            dp[i] = dp[i==0?0:i-1];
            if(nums[i]==target){ 
                dp[i]++;
                cout<<"a "<<i<<" "<<dp[i]<<endl;
                m[sum] = i;
                continue;
            }
            if(m.count(s[i]-target)!=0){
                dp[i]=max(dp[i],dp[m[s[i]-target]]+1);
                cout<<"b "<<i<<" "<<dp[i]<<endl;
            }else if(s[i]==target){
                dp[i]=max(dp[i],1);
                cout<<"c "<<i<<" "<<dp[i]<<endl;
            }
             m[sum] = i;

        }
        return dp[nums.size()-1];
    }
};

leetcode 698. Partition to K Equal Sum Subsets 分支限界

题目

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It’s possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.

思路

dfs 分支限界直接回溯,dfs实际上是考虑到了所有的组合的,所以不用担心排列组合导致的无法划分为k个子集的情况,代码中的 flag 标志计算使用 dfs 递归遍历所有组合

源码

class Solution {
public:
    int avg;
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        for(auto p:nums){
            sum+=p;
        }
        if(sum % k !=0) return false;
        avg =  sum / k;
        vector<bool> vis(nums.size(),false);
        return dfs(nums.size()-1,avg,nums,nums.size(),vis); 
    }
    bool dfs(int start,int target,vector<int> &nums,int remains,vector<bool> &vis){
        if(remains==0)return true;
        bool flag = false;
        for(int i = start;i >= 0;--i){
            if(!vis[i]&&target>=nums[i]){
                vis[i]=true;
                if(target == nums[i])flag = dfs(nums.size()-1,avg,nums,remains-1,vis);
                else flag = dfs(i-1,target-nums[i],nums,remains-1,vis);
                if(flag)return flag;
                vis[i]=false;
               // while(i>=1&&nums[i]==nums[i-1])i--;
            }
        }
        return flag;
    }
};