One-Dimensional DP

One-dimensional DP uses a single state index, but that state may summarize either a count or an optimal value. On a line of positions 0…n with jumps of length 1 or 2, we compute both the number of routes and minimum landing cost. The shared dependency shape highlights why the aggregation operation—sum versus minimum—comes from the question, not from the array dimension.

Prerequisites: Introduction to DP; modular counting; arrays.

Build the idea

1. Recognize the repeated subproblems

   Enumerating all step sequences repeats the same remaining positions. A path’s earlier history is irrelevant after its last landing: future moves depend only on the current index. With n≤100000, one pass over positions is affordable; listing all Fibonacci-many routes is not. If an extra resource such as remaining coupons changed future costs, a single index would no longer be sufficient.

2. Define the state

   ways[i] counts ordered 1/2-jump routes from 0 to i modulo 10^9+7. best[i] is minimum total cost of landing on positive positions on such a route; cost[0]=0. We pay cost[i] once on arrival and may skip positions with a length-2 jump. Costs can be negative because all movement is forward and the state graph remains acyclic.

3. Derive the transition

   A route ending at i came from i−1 or, when i≥2, i−2. The two final-jump classes are disjoint, so add their counts. For cost, choose the smaller predecessor best then add the common landing cost[i]. The minimum cannot sum alternatives, and the count cannot keep only the cheapest predecessor: these answer different questions over the same state graph.

   $$\mathrm{best}\left[i\right]=\mathrm{cost}\left[i\right]+\min \left(\mathrm{best}\right[i-1],\mathrm{best}[i-2\left]\right)$$

4. Base cases and computation order

   ways[0]=1 represents one empty route; best[0]=0 represents its zero cost. Process i=1…n and ignore i−2 when negative. At i=1 only predecessor zero is valid. Each route’s final step points backward, so both arrays have completed dependencies. Modular reduction is used only for counts; optimal costs retain their signed long long values.

5. Correctness and invariant

   Induction by final jump proves the count partition and the optimal-cost recurrence simultaneously. Every valid route has exactly one predecessor class, and replacing its prefix by a cheaper route cannot affect the final jump. This is sufficient state plus optimal substructure, not a claim that Fibonacci formulas solve arbitrary path-cost problems.

6. Work the example

   With costs [10,1,10,1], best values are 0,10,1,11,2 and ways are 1,1,2,3,5. Minimum cost takes 0→2→4, paying 1+1. There are five routes in total, including more expensive ones, so the two printed answers are 5 and 2.

   i	0	1	2	3	4
   ways	1	1	2	3	5
   best	0	10	1	11	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),best(n+1),ways(n+1);
    for(int i=1;i<=n;++i){
        std::cin>>cost[i];
    }
    ways[0]=1;
    for(int i=1;i<=n;++i){
        ways[i]=ways[i-1];
        best[i]=best[i-1];
        if(i>=2){
            ways[i]=(ways[i]+ways[i-2])%1000000007;
            best[i]=std::min(best[i],best[i-2]);
        }
        best[i]+=cost[i];
    } // Pay only for positions actually landed on.
    std::cout<<ways[n]<<' '<<best[n]<<'\n';
}

Complexity analysis

n+1 states in each of two arrays, at most two predecessors: O(n) time and O(n) stored costs/DP values. Both value recurrences can be compressed to two prior states if no reconstruction or table is required. Cost magnitude≤n·10^9 fits long long.

Example input and output

Read n (0..100000), then costs for positions 1..n within ±10^9. Allowed jumps are +1/+2 from zero. Print route count modulo 10^9+7 and minimum landing cost.

Input

4
10 1 10 1

Output

5 2

With costs [10,1,10,1], best values are 0,10,1,11,2 and ways are 1,1,2,3,5. Minimum cost takes 0→2→4, paying 1+1. There are five routes in total, including more expensive ones, so the two printed answers are 5 and 2.

Practical applications

Use for staircase counts, minimum position costs and line-reachability states. Add more dimensions only when needed for information affecting future choices. Reconstruction records the predecessor chosen by the minimum-cost transition.

Check your understanding

Why do ways use addition while best uses minimum?

Put it into practice

Enumerate all routes to position five and calculate each cost.