crescente.cpp

#include <cstdio>

const int maxn = 510;

int dp[maxn][maxn], n;
bool mark[maxn][maxn];

int solve(int pos, int last) {
	if(pos == n) return 1;
	
	if(mark[pos][last]) return dp[pos][last];
	
	for(int i = pos+last+1; i <= n; i++) // já lidamos com as restrições dentro do for para simplificar a implementação
		dp[pos][last] += solve(i, i-pos);
	
	mark[pos][last] = 1;
	
	return dp[pos][last];
}

int main() {
	scanf("%d", &n);
	printf("%d\n", solve(1, 0));
}