### 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.