We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Sherlock and Cost
Sherlock and Cost
+ 0 comments Here is problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-sherlock-and-cost-problem-solution.html
+ 0 comments DP solution with O(n) time and O(1) space complexity (no need to use array to store dp value) Explaination in the comments
def cost(b) low = 0 # low[i] is max cost using first i items, ending with 1 at i-th position high = 0 # high[i] is max cost using first i items, ending with b[i] at i-th position (1..b.length - 1).each do |i| pre_low = low # previous low value pre_high = high # previous high value low = [pre_low, pre_high + (b[i - 1] - 1).abs].max high = [pre_low + (b[i] - 1).abs, pre_high + (b[i] - b[i - 1]).abs].max end [low, high].max end
+ 0 comments #include <bits/stdc++.h> using namespace std; int dp[100001][2];// dp[i][0]represents 1 was selected previously dp[i][1] represents that b[i-1] was selected previously int solve(int i,int choice,vector<int>&b,int n){ if(i==n)return 0; if(dp[i][choice]!=-1)return dp[i][choice]; int ans1,ans2; if(choice){ ans1=abs(b[i]-b[i-1])+solve(i+1,1,b,n); ans2=abs(1-b[i-1])+solve(i+1,0,b,n); return dp[i][choice]=max(ans1,ans2); } else{ ans1=abs(b[i]-1)+solve(i+1,1,b,n); ans2=abs(1-1)+solve(i+1,0,b,n); return dp[i][choice]=max(ans1,ans2); } } int main(){ int t,n; cin>>t; while(t--){ cin>>n; vector<int>b(n); for(int i=0;i<n;i++)cin>>b[i]; if(n==1)cout<<0<<"\n"; else if(n==2)cout<<b[1]-1<<"\n"; else{ for(int i=0;i<=n;i++){ for(int j=0;j<2;j++)dp[i][j]=-1; } cout<<max(solve(1,0,b,n),solve(1,1,b,n))<<"\n"; } } return 0; }
+ 1 comment Recursive problem statement which helped me to understand problem:
cost(B:array) = { len of B is 2 => we take or not take the last element max(abs(B[0] - B[1]), B[0]) len of B > 2 => Take first from B -> B[0] calculate case if next element is taken |B[0] - B[1]| + cost(rest of B) calculcate case if next element is not taken B[0] + cost(take rest of B but replace first with 0) return maximum of these 2 }
Coming from this it is easier to develop iterative approach
+ 0 comments DP O(N) solution
int cost(vector<int> B) { int n = sz(B); vvi dp(N,vi(2,0)); FOR(i,1,n){ dp[i][0] = max(dp[i-1][0],dp[i-1][1] + B[i-1]-1); dp[i][1] = max(dp[i-1][1] + abs(B[i-1]-B[i]), dp[i-1][0] + B[i]-1); } return max(dp[n-1][0],dp[n-1][1]); }
Load more conversations
Sort 245 Discussions, By:
Please Login in order to post a comment