Even Harder
Contest: Codeforces Round 688 (Div. 2)
Difficulty rating: 2700
Tags: dp

Gildong is now developing a puzzle game. The puzzle consists of $$$n$$$ platforms numbered from $$$1$$$ to $$$n$$$. The player plays the game as a character that can stand on each platform and the goal of the game is to move the character from the $$$1$$$-st platform to the $$$n$$$-th platform.

The $$$i$$$-th platform is labeled with an integer $$$a_i$$$ ($$$0 \le a_i \le n-i$$$). When the character is standing on the $$$i$$$-th platform, the player can move the character to any of the $$$j$$$-th platforms where $$$i+1 \le j \le i+a_i$$$. If the character is on the $$$i$$$-th platform where $$$a_i=0$$$ and $$$i \ne n$$$, the player loses the game.

Since Gildong thinks the current game is not hard enough, he wants to make it even harder. He wants to change some (possibly zero) labels to $$$0$$$ so that there remains exactly one way to win. He wants to modify the game as little as possible, so he's asking you to find the minimum number of platforms that should have their labels changed. Two ways are different if and only if there exists a platform the character gets to in one way but not in the other way.

Input format:
Each test contains one or more test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$).

Each test case contains two lines. The first line of each test case consists of an integer $$$n$$$ ($$$2 \le n \le 3000$$$) — the number of platforms of the game.

The second line of each test case contains $$$n$$$ integers. The $$$i$$$-th integer is $$$a_i$$$ ($$$0 \le a_i \le n-i$$$) — the integer of the $$$i$$$-th platform.

It is guaranteed that:

- For each test case, there is at least one way to win initially.
- The sum of $$$n$$$ in all test cases doesn't exceed $$$3000$$$.

Output format:
For each test case, print one integer — the minimum number of different labels that should be changed to $$$0$$$ so that there remains exactly one way to win.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first case, the player can only move to the next platform until they get to the $$$4$$$-th platform. Since there is already only one way to win, the answer is zero.

In the second case, Gildong can change $$$a_2$$$, $$$a_3$$$, and $$$a_4$$$ to $$$0$$$ so that the game becomes $$$4$$$ $$$0$$$ $$$0$$$ $$$0$$$ $$$0$$$. Now the only way the player can win is to move directly from the $$$1$$$-st platform to the $$$5$$$-th platform.

In the third case, Gildong can change $$$a_2$$$ and $$$a_8$$$ to $$$0$$$, then the only way to win is to move in the following way: $$$1$$$ – $$$3$$$ – $$$7$$$ – $$$9$$$.

Example input:
3
4
1 1 1 0
5
4 3 2 1 0
9
4 1 4 2 1 0 2 1 0

Example output:
0
3
2

Editorial:
Since there is at least one way to win initially, every platform is reachable from the start. Note that this condition should still hold after we achieve what Gildong wants. Because of this, if there are multiple $$$j$$$'s where $$$j + a_j \ge i$$$, there are at least two ways that can get to the $$$i$$$-th platform. Therefore, in order to leave only one way to get to the $$$i$$$-th platform, we need to change all $$$a_j$$$'s where $$$j + a_j >= i$$$ into $$$0$$$ except for one of them. We'll call this process cleaning, and the platforms where we set $$$a_j = 0$$$ are the cleaned platforms.
Let $$$dp[i][x]$$$ ($$$i \le x$$$) be the minimum number of platforms that should be cleaned to leave only one way to get to the $$$i$$$-th platform, where the only platform $$$k$$$ that can directly move to the $$$i$$$-th platform (i.e. the predecessor) has a value at most $$$x - k$$$. In other words, $$$dp[i][x]$$$ only considers all $$$k$$$'s where $$$k \lt i \le k + a_k \le x$$$, and choose the one that requires minimum number of cleaned platforms so far. We'll determine $$$dp[i][i..n]$$$ in increasing order of $$$i$$$.
Now let $$$cnt$$$ be the number of $$$y$$$'s where $$$j \lt y \lt i$$$ and $$$y + a_y \ge i$$$. Initially $$$cnt$$$ is $$$0$$$. Now for each $$$j$$$ from $$$i - 1$$$ to $$$1$$$ (downwards), if $$$j + a_j >= i$$$, minimize $$$dp[i][j + a_j]$$$ with $$$dp[j][i - 1] + cnt$$$ and then increase $$$cnt$$$ by $$$1$$$. This means we clean all platforms between $$$j + 1$$$ and $$$i - 1$$$ to let the $$$j$$$-th platform be the predecessor of the $$$i$$$-th platform, while it has possibility to reach the $$$j + a_j$$$-th platform. Note that all $$$k$$$'s where $$$k \lt j$$$ and $$$k + a_k \ge i$$$ are already cleaned when calculating $$$dp[j][i - 1]$$$, so we only need to count the cleaned platforms between $$$j + 1$$$ and $$$i - 1$$$ for $$$cnt$$$.
Then we can prefix-minimize $$$dp[i][i..n]$$$ because the actual meaning of the $$$dp[i][x]$$$ is the minimum number of platforms that should be cleaned for the predecessor of the $$$i$$$-th platform can reach at most the $$$x$$$-th platform; i.e. it should consider all cases where $$$j + a[j] \lt x$$$ as well.
After we repeat these processes for all $$$i$$$'s, the answer is $$$dp[n][n]$$$. Though the explanation is quite complicated, the code turns out to be very short.
Time complexity: $$$\mathcal{O}(n^2)$$$.