첫번째 소스코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;



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

	vector<int>v(n);
	vector<int>time(n);
	vector<int>dp(n);

	for (int i = 0; i < n; i++)
	{
		cin >> time[i];
		cin >> v[i];
		dp[i] = v[i];
	}

	int answer = 0;

	for (int i = 0; i < n; i++)
	{
		int nextIdx = time[i] + i;

		if (nextIdx < n)
		{
			dp[nextIdx] = max(dp[nextIdx], v[nextIdx] + dp[i]);
			answer = max(answer, dp[nextIdx]);
		}

	}

	cout << answer;

}

-> 테스트 케이스 2번, 4번 틀린다.

https://www.acmicpc.net/source/34371202

점화식

dp[i] : i번부터 마지막날까지 낼수 있는 최대 수익인데,,
dp[i] = max(dp[i + time[i]] + v[i], maxvalue)인데
dp[1] = max(dp[4] + v[1], maxvalue) 라고 할때

문제점이 순차적으로 진행하면 dp[1]에서 끝나므로 뒤에 오는 인덱스들에 영향을
전혀 주지 못하게 된다.
즉 dp[4]가 먼저 계산이 된상태에서 진행이 되어야 한다.
그렇게 만들기 위해서는 역순으로 진행되어야 한다!