just_for_one's blog

By just_for_one, history, 7 weeks ago, In English

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?

 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by just_for_one (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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]