对于第 $i$ 个数字，只有两种情况：取和不取。
如果取第 $i$ 个数字，那么需要判断一下第 $i$ 个数字是否是在第 $j$ 个位置上，满足条件则用上一个数字的状态+1，不满足则直接赋值成上一个数字的状态。(上一个数字的状态为 $DP[i-1][j-1]$ )
如果不取第 $i$ 个数字，直接把当前状态赋值成上一个数字在 $j$ 位置的状态( $DP[i-1][j]$ )。

可得状态转移方程 $DP[i][j]=Max(DP[i-1][j], DP[i-1][j-1] + (a[j]==j))$
两者取最优解

以题中样例来说明：一共五个数：1 1 2 5 4：

当输入第一个数字 1 时：
判断1是否是第一个位置， $DP[1][1] = DP[0][0] + 1 = 1$ 。由于只输入了一个数字，所以只更新一个状态
当输入第二个数字 1 时：
判断1是否是第一个位置，根据状态转移方程， $DP[2][1]=DP[1][1] = 1$
再判断1是否是第二个位置，根据状态转移方程， $DP[2][2]=DP[1][1]+0 = 1$
当输入第三个数字 2 时：
判断2是否是第一个位置，根据状态转移方程， $DP[3][1]=DP[2][1] = 1$
再判断2是否是第二个位置，根据状态转移方程， $DP[3][2]=DP[2][1]+1 = 2$
再判断2是否是第三个位置，根据状态转移方程， $DP[3][3]=DP[2][2]+0 = 1$
当输入第四个数字 5 时：
判断5是否是第一个位置，根据状态转移方程， $DP[4][1]=DP[3][1] = 1$
再判断5是否是第二个位置，根据状态转移方程， $DP[4][2]=DP[3][2] = 2$
再判断5是否是第三个位置，根据状态转移方程， $DP[4][3]=DP[3][2] + 0 = 2$
再判断5是否是第四个位置，根据状态转移方程， $DP[4][4]=DP[3][3] + 0 = 1$
当输入第五个数字 4 时：
判断4是否是第一个位置，根据状态转移方程， $DP[5][1]=DP[4][1] = 1$
再判断4是否是第二个位置，根据状态转移方程， $DP[5][2]=DP[4][2] = 2$
再判断4是否是第三个位置，根据状态转移方程， $DP[5][3]=DP[4][2] + 0 = 2$
再判断4是否是第四个位置，根据状态转移方程， $DP[5][4]=DP[4][3] + 1 = 3$
再判断4是否是第五个位置，根据状态转移方程， $DP[5][5]=DP[4][4] + 0 = 1$

数字\位置	1	2	3	4	5
$a[1]$ : 1	1	0	0	0	0
$a[2]$ : 1	1	1	0	0	0
$a[3]$ : 2	1	2	1	0	0
$a[4]$ : 5	1	2	2	1	0
$a[5]$ : 4	1	2	2	3	1

代码：

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int a[1010], dp[1010][1010];

int main()
{
    int n;
    cin>>n;

    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + (a[i] == j));
            ans = max(ans, dp[i][j]);
        }
    }

    cout<<ans;
    return 0;
}

优化：

根据DP的更新过程可以看出，当前状态只与上一个数字的状态有关，所以可以尝试将二维数组优化为一维数组。