Count Paths on a Line
EasyPractice library · +10 XPdynamic programmingrecursioncounting
You are at position 0 on a number line. You want to reach position N. In one step, you can move 1 or 2 positions forward. Given N, count the number of distinct ways to reach position N.
Input
A single integer N.
Output
A single integer representing the number of distinct ways to reach position N.
Constraints
1 <= N <= 1000
Time limit 1 s (native code; slower languages get more)Memory 256 MB12 hidden tests
Example 1
Input
3
Output
3
Ways to reach 3: (0->1->2->3), (0->1->3), (0->2->3). Total 3 ways.
Example 2
Input
4
Output
5
Ways to reach 4: (0->1->2->3->4), (0->1->2->4), (0->1->3->4), (0->2->3->4), (0->2->4). Total 5 ways.
Hints
Similar problems
- Count Subsequences Summing to KEasy
- Longest Increasing Subsequence on a PermutationHard
- Longest Zigzag SubsequenceMedium
- Maximum Sum Non-Adjacent PairsMedium
- Maximum Sum Increasing SubsequenceMedium
- Lexicographically Smallest PathMedium
More topics: Hash Map and Hashing problems, Dynamic Programming problems, Recursion problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
3
Example 2 input
4