C++ "General" DP Solution (N Non-overlapping sub-arrays)
What if the problem changes to find N Non-overlapping Sub-arrays Each With Target Sum, instead of two?\n\nI would like to provide a more General solution here:\
What if the problem changes to find **N** Non-overlapping Sub-arrays Each With Target Sum, **instead of two**?\n\nI would like to provide a more **General** solution here:\n\nDenote `dp[i][j]` as: \nWe are only using `arr[1,2,...,i]`, and we have found `j` non-overlapping sub-arrays with target sum. The value of `dp[i][j`] is the minimum sum of the lengths of the sub-arrays.\n\nThen we have the equation:\n```\ndp[i][j] = min(dp[i-1][j], dp[d][j-1] + i - d)\n```\n\nExplanation:\n1. `dp[i][j] <= dp[i-1][j]`: \nThis is because, we are considering more elements than before, hence the result can only be better (the length is smaller).\n2. `dp[d][j-1] + i - d`: \nThe `d` here is the index satisfying `sum(arr[i-d+1,...,i]) = target`. This sub-array has length = `i-d`.\nTo ensure the sub-arrays don\'t overlap, the rest of the sub-arrays must use index `<= d`, hence this is why we use `dp[d][j-1]` here.\nTo quickly find such `d`, use a unordered_map to keep track of the prefix sum.\n\nIn the code:\nNotice that we are using index from 1 to n, hence we can easily use index 0 to prevent extra checking.\nAlso notice that we are initializing `dp[i][0] = 0`, because if we can\'t find any subarray, the sum of length must be 0.\n\nThen, the answer is given by` dp[n][j]`. In this problem,` j = 2`.\n\n```\nclass Solution {\npublic:\n    int dp[100005][3];  //if asking for n subarrays, change 3 to n+1\n    unordered_map<int,int> sm;  // keep track of (prefixsum : index)  \n    \n    int minSumOfLengths(vector<int>& arr, int tar) {\n        int n = arr.size(), cursum = 0;\n        sm[0] = 0;\n        memset(dp, 127, sizeof(dp));  //initialize to INF\n        for (int i = 0; i < 100005; i++) dp[i][0] = 0;  //if we doesn\'t find a subarray, len = 0\n        \n        for (int i = 1; i <= n; i++) {\n            int d = -1;  //initialize to -1\n            cursum += arr[i-1];\n            sm[cursum] = i;\n            if (sm.count(cursum - tar)) d = sm[cursum-tar];\n            \n            for (int j = 1; j <= 2; j++) {  // if asking for n subarrays, change 2 to n\n                dp[i][j] = min(dp[i][j], dp[i-1][j]);  //dp[i][j] must <= dp[i-1][j]\n                if (d != -1) dp[i][j] = min(dp[i][j],dp[d][j-1] + i - d);\n            }\n        }\n        if (dp[n][2] > 1e9) return -1;   // if asking for n subarrays, change 2 to n\n        return dp[n][2];   // if asking for n subarrays, change 2 to n\n    }\n};\n```
['Dynamic Programming', 'C']