Reconstructing DP Solutions

An optimal value does not necessarily tell a user what to choose. Reconstruction records which transition attained each optimum, then follows those choices backward. We revisit minimum-cost 1/2-jump routes and output an actual path including position zero. The idea generalizes to selected knapsack items, grid paths, subsequences and parse trees, but each witness must follow the original state meaning.

Prerequisites: One-Dimensional DP; vectors and reversing. Related existing lessons: Tree Traversals (DFS and BFS).

Build the idea

1. Recognize the repeated subproblems

   The value DP merges all histories at a position because only the best cost matters for continuing. That merging loses the concrete route unless an attaining decision is retained. Brute-force path storage in every state would duplicate long prefixes and can use quadratic memory. A single predecessor index per state is enough to recover one route afterward.

2. Define the state

   dp[i] is minimum landing cost from 0 to i; parent[i] is the previous position selected for that optimum. parent[0]=−1 is the end-of-backtrack marker. A parent points to an entire already-optimized smaller state, so it implicitly stores a persistent shared prefix without copying a path vector at every update.

3. Derive the transition

   Compare dp[i−1] and, when present, dp[i−2]. Choose the cheaper predecessor and set dp[i]=cost[i]+dp[parent[i]]. Ties prefer i−1 in this implementation; that defines a deterministic witness but does not promise the fewest jumps or lexicographically smallest route among all minimum-cost solutions. Such secondary objectives must be encoded explicitly if required.

   $$\mathrm{dp}\left[i\right]=\mathrm{cost}\left[i\right]+\mathrm{dp}\left[\mathrm{parent}\right[i\left]\right]$$

4. Base cases and computation order

   Start dp[0]=0 and fill increasing i. Store the parent at the same time as the winning transition. Starting from n, push the current position and replace it by its parent until −1, then reverse. Every positive parent index strictly decreases, so backtracking terminates; zero is included exactly once. For n=0 the valid route is simply [0].

5. Correctness and invariant

   Induction ensures each parent transition attains the true dp value. Following the chain therefore produces only legal +1/+2 jumps with total cost dp[n]. The chain cannot invent an unchosen transition. Storing choices in a compressed in-place DP can be subtler: overwritten predecessor states may refer to a later item layer, so a reconstruction proof must track versions rather than assuming every parent scheme is safe.

6. Work the example

   Costs [10,1,10,1] yield dp=[0,10,1,11,2]. Parents for positions 1…4 are 0,0,2,2. Backtracking 4→2→0 then reversing gives 0→2→4 and cost 2. The table pairs each optimum with its selected predecessor so the output can be checked manually.

   position	0	1	2	3	4
   dp	0	10	1	11	2
   parent	−1	0	0	2	2

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n;
    std::cin>>n;
    std::vector<long long>cost(n+1),dp(n+1);
    std::vector<int>parent(n+1,-1);
    for(int i=1;i<=n;++i){
        std::cin>>cost[i];
    }
    for(int i=1;i<=n;++i){
        parent[i]=i-1;
        if(i>=2&&dp[i-2]<dp[i-1]){
            parent[i]=i-2;
        }
        dp[i]=cost[i]+dp[parent[i]];
    } // Store the predecessor of the chosen transition.
    std::vector<int>path;
    for(int i=n;i!=-1;i=parent[i]){
        path.push_back(i);
    }
    std::reverse(path.begin(),path.end());
    std::cout<<dp[n]<<'\n';
    for(int i=0;i<(int)path.size();++i){
        std::cout<<path[i]<<(i+1==(int)path.size()?'\n':' ');
    }
}

Complexity analysis

O(n) value/parent computation and O(n) worst-case backtracking/output. O(n) costs, values, parents and route storage. Storing only two values could compute the optimum but would lose this direct witness chain.

Example input and output

Read n (0..100000) and n landing costs within ±10^9. Jumps are +1/+2 from zero. Print minimum cost, then visited positions in forward order including 0 and n.

Input

4
10 1 10 1

Output

2
0 2 4

Costs [10,1,10,1] yield dp=[0,10,1,11,2]. Parents for positions 1…4 are 0,0,2,2. Backtracking 4→2→0 then reversing gives 0→2→4 and cost 2. The table pairs each optimum with its selected predecessor so the output can be checked manually.

Practical applications

Use when the task asks for a witness as well as a number. Alternatives include retaining the full table and backtracking equality conditions, rerunning DP on smaller regions, or specialized divide-and-conquer reconstruction when memory is tight.

Check your understanding

What does parent[i] need to guarantee?

Put it into practice

Add equal-cost ties and check that every printed jump is legal and costs sum correctly.