P4 跳格⼦ - Hopscotch

#include <iostream>
using namespace std;

const long long MOD = 1e9 + 7;
long long N, a[500005], dp[500005], ans;

long long dfs(int i)
{
	if(dp[i])	return dp[i];
	
	for(int j = i+1; j < N; ++j)
		if(abs(a[i] - a[j]) <= 2)
			dp[i] = (dp[i] + dfs(j)) % MOD;
	
	dp[i] = (dp[i] + 1) % MOD;
	ans = (ans + dp[i]) % MOD;
	return dp[i];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    for(int i = 0; i < N; ++i)	cin >> a[i];
    for(int i = 0; i < N; ++i)
    	if(dp[i] == 0)
    		dfs(i);
    		
    cout << ans << "\n";
}