8000 dp on subsequence · Jashans254/DSA_cpp@f3f4b1e · GitHub
[go: up one dir, main page]
Skip to content

Commit f3f4b1e

Browse files
author
jashanpreet singh
committed
dp on subsequence
1 parent f08cb41 commit f3f4b1e

34 files changed

+1855
-1
lines changed

‎DP/lec10_40.cpp

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
//{ Driver Code Starts
2+
3+
#include <bits/stdc++.h>
4+
using namespace std;
5+
6+
7+
// } Driver Code Ends
8+
9+
// User function template for C++
10+
11+
class Solution {
12+
public:
13+
14+
bool f(int ind , int target , vector<int> &arr){
15+
if(target == 0 ) return true;
16+
17+
if( ind == 0 ) return ( arr[0] == target);
18+
19+
bool notTake = f(ind - 1 , target , arr);
20+
bool take = false;
21+
if(arr[ind] <=target) take = f( ind-1 , target-arr[ind],arr);
22+
return take | notTake;
23+
}
24+
bool isSubsetSum(vector<int>& arr, int target) {
25+
// code here
26+
int n = arr.size();
27+
return f(n-1 , target , arr);
28+
}
29+
};
30+
31+
32+
//{ Driver Code Starts.
33+
34+
int main() {
35+
36+
int t;
37+
cin >> t;
38+
cin.ignore();
39+
while (t--) {
40+
vector<int> arr;
41+
string input;
42+
getline(cin, input);
43+
stringstream ss(input);
44+
int number;
45+
while (ss >> number) {
46+
arr.push_back(number);
47+
}
48+
int sum;
49+
cin >> sum;
50+
cin.ignore();
51+
52+
Solution ob;
53+
if (ob.isSubsetSum(arr, sum))
54+
cout << "true" << endl;
55+
else
56+
cout << "false" << endl;
57+
cout << "~" << endl;
58+
}
59+
return 0;
60+
}
61+
62+
// } Driver Code Ends

‎DP/lec10_41.cpp

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
//{ Driver Code Starts
2+
3+
#include <bits/stdc++.h>
4+
using namespace std;
5+
6+
7+
// } Driver Code Ends
8+
9+
// User function template for C++
10+
11+
class Solution {
12+
public:
13+
14+
bool f(int ind , int target , vector<int> &arr,vector<vector<int>>&dp){
15+
if(target == 0 ) return true;
16+
17+
if( ind == 0 ) return ( arr[0] == target);
18+
19+
if(dp[ind][target]!= -1) return dp[ind][target];
20+
bool notTake = f(ind - 1 , target , arr,dp);
21+
bool take = false;
22+
if(arr[ind] <=target) take = f( ind-1 , target-arr[ind],arr,dp);
23+
return dp[ind][target]=take | notTake;
24+
}
25+
bool isSubsetSum(vector<int>& arr, int target) {
26+
// code here
27+
int n = arr.size();
28+
29+
vector<vector<int>>dp( n+1 , vector<int>(target+1 , -1));
30+
return f(n-1 , target , arr,dp);
31+
}
32+
};
33+
34+
35+
//{ Driver Code Starts.
36+
37+
int main() {
38+
39+
int t;
40+
cin >> t;
41+
cin.ignore();
42+
while (t--) {
43+
vector<int> arr;
44+
string input;
45+
getline(cin, input);
46+
stringstream ss(input);
47+
int number;
48+
while (ss >> number) {
49+
arr.push_back(number);
50+
}
51+
int sum;
52+
cin >> sum;
53+
cin.ignore();
54+
55+
Solution ob;
56+
if (ob.isSubsetSum(arr, sum))
57+
cout << "true" << endl;
58+
else
59+
cout << "false" << endl;
60+
cout << "~" << endl;
61+
}
62+
return 0;
63+
}
64+
65+
// } Driver Code Ends

‎DP/lec10_42.cpp

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
//{ Driver Code Starts
2+
3+
#include <bits/stdc++.h>
4+
using namespace std;
5+
6+
7+
// } Driver Code Ends
8+
9+
// User function template for C++
10+
11+
class Solution {
12+
public:
13+
14+
bool f(int ind , int target , vector<int> &arr,vector<vector<int>>&dp){
15+
if(target == 0 ) return true;
16+
17+
if( ind == 0 ) return ( arr[0] == target);
18+
19+
if(dp[ind][target]!= -1) return dp[ind][target];
20+
bool notTake = f(ind - 1 , target , arr,dp);
21+
bool take = false;
22+
if(arr[ind] <=target) take = f( ind-1 , target-arr[ind],arr,dp);
23+
return dp[ind][target]=take | notTake;
24+
}
25+
bool isSubsetSum(vector<int>& arr, int target) {
26+
// code here
27+
int n = arr.size();
28+
29+
// 2D DP Table
30+
vector<vector<bool>> dp(n, vector<bool>(target + 1, false));
31+
32+
// Base Case: Sum 0 is always possible
33+
for (int i = 0; i < n; i++) dp[i][0] = true;
34+
35+
// Base Case: If first element is within target range
36+
if (arr[0] <= target) dp[0][arr[0]] = true;
37+
38+
// Bottom-Up DP
39+
for (int ind = 1; ind < n; ind++) {
40+
for (int i = 1; i <= target; i++) {
41+
bool notTake = dp[ind - 1][i]; // Exclude current element
42+
bool take = false;
43+
if (arr[ind] <= i)
44+
take = dp[ind - 1][i - arr[ind]]; // Include current element
45+
46+
dp[ind][i] = take || notTake; // Store result
47+
}
48+
}
49+
50+
return dp[n - 1][target]; // Final answer
51+
}
52+
};
53+
54+
55+
//{ Driver Code Starts.
56+
57+
int main() {
58+
59+
int t;
60+
cin >> t;
61+
cin.ignore();
62+
while (t--) {
63+
vector<int> arr;
64+
string input;
65+
getline(cin, input);
66+
stringstream ss(input);
67+
int number;
68+
while (ss >> number) {
69+
arr.push_back(number);
70+
}
71+
int sum;
72+
cin >> sum;
73+
cin.ignore();
74+
75+
Solution ob;
76+
if (ob.isSubsetSum(arr, sum))
77+
cout << "true" << endl;
78+
else
79+
cout << "false" << endl;
80+
cout << "~" << endl;
81+
}
82+
return 0;
83+
}
84+
85+
// } Driver Code Ends

‎DP/lec10_43.cpp

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
//{ Driver Code Starts
2+
3+
#include <bits/stdc++.h>
4+
using namespace std;
5+
6+
7+
// } Driver Code Ends
8+
9+
// User function template for C++
10+
11+
class Solution {
12+
public:
13+
14+
15+
bool isSubsetSum(vector<int>& arr, int target) {
16+
17+
18+
int n = arr.size();
19+
20+
// Optimized DP arrays (previous & current row)
21+
vector<bool> prev(target + 1, false), cur(target + 1, false);
22+
23+
// Base case: Sum 0 is always possible
24+
prev[0] = cur[0] = true;
25+
26+
// If first element is within range, mark it
27+
if (arr[0] <= target) prev[arr[0]] = true;
28+
29+
// Bottom-Up DP
30+
for (int ind = 1; ind < n; ind++) {
31+
for (int i = 1; i <= target; i++) {
32+
bool notTake = prev[i]; // Exclude current element
33+
bool take = false;
34+
if (arr[ind] <= i)
35+
take = prev[i - arr[ind]]; // Include current element
36+
37+
cur[i] = take || notTake; // Store result
38+
}
39+
prev = cur; // Move current row to previous
40+
}
41+
42+
return prev[target]; // Final answer
43+
}
44+
};
45+
46+
47+
//{ Driver Code Starts.
48+
49+
int main() {
50+
51+
int t;
52+
cin >> t;
53+
cin.ignore();
54+
while (t--) {
55+
vector<int> arr;
56+
string input;
57+
getline(cin, input);
58+
stringstream ss(input);
59+
int number;
60+
while (ss >> number) {
61+
arr.push_back(number);
62+
}
63+
int sum;
64+
cin >> sum;
65+
cin.ignore();
66+
67+
Solution ob;
68+
if (ob.isSubsetSum(arr, sum))
69+
cout << "true" << endl;
70+
else
71+
cout << "false" << endl;
72+
cout << "~" << endl;
73+
}
74+
return 0;
75+
}
76+
77+
// } Driver Code Ends

‎DP/lec10_44.cpp

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
class Solution {
2+
public:
3+
// Helper function: Checks if a subset with the given target sum exists
4+
bool isSubsetSum(vector<int>& arr, int target) {
5+
int n = arr.size();
6+
7+
// Optimized DP arrays (previous & current row)
8+
vector<bool> prev(target + 1, false), cur(target + 1, false);
9+
10+
// Base case: Sum 0 is always possible
11+
prev[0] = cur[0] = true;
12+
13+
// If first element is within range, mark it
14+
if (arr[0] <= target) prev[arr[0]] = true;
15+
16+
// Bottom-Up DP
17+
for (int ind = 1; ind < n; ind++) {
18+
for (int i = 1; i <= target; i++) {
19+
bool notTake = prev[i]; // Exclude current element
20+
bool take = false;
21+
if (arr[ind] <= i)
22+
take = prev[i - arr[ind]]; // Include current element
23+
24+
cur[i] = take || notTake; // Store result
25+
}
26+
prev = cur; // Move current row to previous
27+
}
28+
29+
return prev[target]; // Final answer
30+
}
31+
32+
// Main function: Checks if the array can be partitioned into two equal subsets
33+
bool canPartition(vector<int>& arr) {
34+
int n = arr.size();
35+
int totSum = accumulate(arr.begin(), arr.end(), 0);
36+
37+
// If total sum is odd, partitioning is not possible
38+
if (totSum % 2 != 0) return false;
39+
40+
int target = totSum / 2;
41+
return isSubsetSum(arr, target);
42+
}
43+
};
44+

‎DP/lec10_45.cpp

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
class Solution {
2+
public:
3+
int minimumDifference(vector<int>& arr) {
4+
int n = arr.size();
5+
6+
int totSum = accumulate(arr.begin(), arr.end(), 0); // Efficient sum calculation
7+
int k = totSum;
8+
9+
vector<vector<bool>> dp(n, vector<bool>(k + 1, false));
10+
11+
// Base case: sum 0 is always possible
12+
for (int i = 0; i < n; i++) dp[i][0] = true;
13+
14+
// Only mark dp[0][arr[0]] if it's within bounds
15+
if (arr[0] <= k) dp[0][arr[0]] = true;
16+
17+
// DP filling
18+
for (int ind = 1; ind < n; ind++) {
19+
for (int target = 1; target <= k; target++) {
20+
bool notTake = dp[ind - 1][target];
21+
bool take = false;
22+
23+
if (arr[ind] <= target)
24+
take = dp[ind - 1][target - arr[ind]];
25+
26+
dp[ind][target] = take || notTake;
27+
}
28+
}
29+
30+
// Finding the minimum partition difference
31+
int mini = INT_MAX;
32+
for (int s1 = 0; s1 <= totSum / 2; s1++) {
33+
if (dp[n - 1][s1]) {
34+
mini = min(mini, abs((totSum - s1) - s1));
35+
}
36+
}
37+
return mini;
38+
}
39+
};
40+

0 commit comments

Comments
 (0)
0