DP Problem Doubt Atcoder Educational DP Contest

help
,
1

Problem - A - Frog 1

My solution - Submission #6893436 - Educational DP Contest

Doubt - What would be the smart approach to modify my solution if they also wanted to print the path that i chose as well as the minimum cost?

Example -
I/P →
6
30 10 60 10 60 50
O/P->
If we follow the path 11 → 33 → 55 → 66, the total cost incurred would be |30−60|+|60−60|+|60−50|=40|30−60|+|60−60|+|60−50|=40.

2

Make an array initialize arr[i]=i.Then for each elements update who is its parent .Then from nth element go back until parent of the element is the same element.