int dp[10000]; //yeah, you have to know MAXN, here. We assume N < 10000

for (int i = 1; i <= N; i++) {
    dp[i] = 1 + dp[i - 1] + dp[i - 1];
}