How is the recurrence relation handling edge case

#1

the recursive relation for this problem goes something like this dp[i]=min(f(i-1),f(i-2),f(i-3))+arr[i]…how will this recurrence relation assure that we are not choosing 3 consecutive elements …

#2

@neha_153
since we are minimizing the sum, choosing 3 consecutive elements would not be ideal.

#3

for example 1,2,2,5,7 the dp array looks some thing like this…1,2,2,6,9 so ans is 9 but i can consider a[0],a[1],a[3] which will give 8 as ans

1 Like
#4

@neha_153
the answer would be 2 in the case you mentioned.
You missed a small detail in the solution, the final ans would be min({dp[n - 1], dp[n - 2], dp[n - 3]}).

int n; cin >> n;
vector<int> a(n);
for (auto &it : a)
	cin >> it;
vector<int> dp(n);
dp[0] = a[0];
dp[1] = a[1];
dp[2] = a[2];
for (int i = 3 ; i < n; i++) {
	dp[i] = min({dp[i - 1], dp[i - 2], dp[i - 3]}) + a[i];
}
cout << min({dp[n - 1], dp[n - 2], dp[n - 3]});
#5

can you give me the dp array by using that recuurence relation

#6

You can run the code and you’ll get the dp array.

#7

i did it …but can u tell me why are we takng min (dp[n-1],dp[n-2],dp[n-3]) in the last step instead of dp[n-1]

#8

Because dp[i] means the cost of the array selecting a[i]… For final ans you have 3 possibility, i.e you will select any 1 of the last, second last and third last.

#9

ok
got it …thanks!!!

1 Like