Introduction to Dynamic Programming

Dynamic programming evaluates recurring states once and reuses their answers. It replaces a large decision tree with a smaller dependency graph. We minimize the number of jumps of length 1,3 or 4 needed to reach a target. The example introduces the full workflow: identify repeated futures, define a sufficient state, derive choices, initialize a base and choose an order that respects dependencies.

Prerequisites: Loops, arrays, recursion basics and complexity. Related existing lessons: Brute Force and Complete Search.

Build the idea

1. Recognize the repeated subproblems

   A brute-force recursion tries every final jump. Many histories arrive at the same remaining distance and solve exactly the same future problem again. With only a target up to 100000, exponentially many sequences are unreasonable, while one state per distance is manageable. DP is promising when different histories share a small description of what matters next; remembering the entire history would forfeit that reduction.

2. Define the state

   dp[x] is the minimum number of allowed jumps whose total length is exactly x. Earlier choices do not matter beyond their total: every continuation has the same jump options. This is optimal substructure—an optimal full sequence uses an optimal smaller remainder after removing its last jump. The state is an integer distance, not a particular sequence of jumps.

3. Derive the transition

   Partition nonempty solutions by their final jump s∈{1,3,4}. Removing it leaves total x−s, so that class has best value 1+dp[x−s]. Take the minimum over s≤x. Every valid sequence belongs to a final-jump class, and appending that jump constructs a valid candidate, proving neither an option nor its cost is omitted.

   $$\mathrm{dp}\left[x\right]=\min \{1+\mathrm{dp}[x-s]:s\in \{1,3,4\},s\le x\}$$

4. Base cases and computation order

   dp[0]=0 because no jumps reach zero. Initialize other entries to n+1, larger than any needed count, then fill x=1…n. Positive jump lengths guarantee all dependencies have smaller indices and have already been computed. Length 1 makes every state reachable; other problems need a genuine unreachable sentinel and a guard before arithmetic on it.

5. Correctness and invariant

   Induct on x. The base is correct. For a positive x, every solution removes to an already-optimal smaller state, so it cannot beat the recurrence; a minimizing predecessor plus its final jump achieves that recurrence. Greedy largest-jump-first fails at x=6: 4+1+1 uses three jumps while 3+3 uses two. DP retains alternatives rather than making an unsupported commitment.

6. Work the example

   For target 6, the values for distances 0…6 are 0,1,2,1,1,2,2. State 6 compares dp[5]+1=3, dp[3]+1=2, dp[2]+1=3 and keeps 2. The table shows values rather than jump sequences; reconstructing a witness is a later lesson.

   x	0	1	2	3	4	5	6
   dp[x]	0	1	2	1	1	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<int>dp(n+1,n+1);
    dp[0]=0;
    for(int x=1;x<=n;++x){
        for(int step:{1,3,4}){
            if(step<=x){
                dp[x]=std::min(dp[x],1+dp[x-step]); // Final jump partitions all solutions.
            }
        }
    }
    std::cout<<dp[n]<<'\n';
}

Complexity analysis

n+1 states, at most three transitions per state: O(n) time and O(n) array space. A bounded window could compress memory here, but the full table makes state dependencies visible.

Example input and output

Read target n in 0..100000. Print the minimum number of jumps of lengths 1,3,4 totaling n.

Input

6

Output

2

For target 6, the values for distances 0…6 are 0,1,2,1,1,2,2. State 6 compares dp[5]+1=3, dp[3]+1=2, dp[2]+1=3 and keeps 2. The table shows values rather than jump sequences; reconstructing a witness is a later lesson.

Practical applications

Use DP when repeated subproblems and a sufficient compact state are visible. Greedy requires a separate safe-choice proof; brute force can be an oracle for tiny cases. Constraints help decide whether the proposed state space is affordable.

Check your understanding

Why can histories with the same total x share one dp[x]?

Put it into practice

Enumerate jump sequences for targets up to ten and compare their minimum lengths.