Given 2 arrays, array A (containing only 0s and 1s) and the other cost array B of the same size. We needed to convert all the elements of array A to 1 in minimum cost. For every ith element in the array A, converting from 0 to 1 requires B[i] cost but if A[i-1] and A[i+1] are 1 then A[i] can be converted to 1 with 0 cost. Return the minimum possible cost to convert all 0s to 1s. My approach- Isn't this simply $$$dp[i]=min(dp[i-1],dp[i-2])+cost[i]$$$;
Can someone please confirm?
Auto comment: topic has been updated by just_for_one (previous revision, new revision, compare).
let dp[i]=ans for arr[0....i] There will be two case case1 arr[i]=1, then dp[i]=dp[i-1] case2 arr[i]=0, then dp[i]=dp[i-2]+cost[i]
don't think dp would work here, how you will track for i+1 ??
instead, build a min Heap{cost,index} and update considering the i-1, and i+1 and a[i] value.
DP works perfectly well and this post is 5 months old.
the main constraint is this that you cant leave two consecutive zeros without being buyed. so you can make recursive calls with taking into account the state of last index that you buyed that zero or not