[Solved] c++ platforms solving with dynamic programming

by


To restore path:

Store additional n-sized array, say, prev[n], prev[0]=-1. If your dp decides for i’th step that you came from i-1, (i.e. dp[i – 1] + abs(v[i] – v[i – 1]) was larger than dp[i – 2] + 3 * abs(v[i] – v[i – 2])), then prev[i]=i - 1, otherwise prev[i]=i - 2. Then starting from n-1’th element (assuming that your numeration starts from 0), build the path using prev.

Code snippet:

int v = n - 1;
while(v != -1) {
    path.push_back(v + 1);
    v = prev[v];
}
std::reverse(path.begin(), path.end());

1

solved c++ platforms solving with dynamic programming