PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY
PREREQUISITES:
DYNAMIC PROGRAMMING
PROBLEM:
You start from 0. Each step you can choose to go right by a_{i} or left by a_{i}. What is the number of awys to end in [l, r]?
EXPLANATION:
Subtask 1 can be solved in O(2^{n} \cdot n) by trying all possible ways to perform the moves.
To solve subtask 2, we let dp[i][j] denote the number of ways to end in number j after the i-th move. Now, the transition is dp[i][j] = dp[i][j+a[i]] + dp[i][j-a[i]].
This solution works in O(n \cdot Sum of a_{i}) time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.