DP problem looking for approach
How to approach this dynamic programming problem If any body could tell thanks in advance
a bit of recursive or bottom up code would be really help full to me
You can actually check other’s solutions to the problem by navigating to the standing tab just above the problem’s name.
Here is one of the solution
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<iostream>
#include<sstream>
using namespace std;
int n, k;
int a[100000+50];
int b[100000+50], c[100000+50];
int main() {
freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
b[0] = 0;
for(int i=1; i<=n; i++) b[i] = b[i-1] + (a[i] >= 0);
c[n+1] = 0;
for(int i=n; i>=1; i--) c[i] = c[i+1] + (a[i] <= 0);
int ans = n;
for(int i=1; i<n; i++) {
int v = b[i] + c[i+1];
if(v < ans) ans = v;
}
printf("%d\n", ans);
return 0;
}`
1 Like
The problem has a DP tag, but my approach was not exactly a DP one. My thought was to determine, in each step, what would be less costly for you, converting all negative (or zeros) to positive or converting all positives(or zeros) to negative. Not forgetting the fact that we need to have at least one negative(that would be at the beginning of the array) and one positive (that would at the end of the array).
Here is the code for reference:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, k = 0, p = 0, res;
cin >> n;
vector<int> v(n+1);
res = n;
for(int i=1;i<=n;i++) {
cin >> v[i];
if (v[i] <= 0) k++;
}
for(int i=1; i<n; i++) {
if(v[i] >= 0) p++;
if(v[i] <= 0) k--;
res = min(res, p+k);
}
cout << res << "\n";
return 0;
}
1 Like
Thank you so much friend I tried running with actual values and i am able visualise it now thanks yr
1 Like
really help full thanks yr easy to understand
1 Like