큰 수 만들기

https://programmers.co.kr/learn/courses/30/lessons/12913
기본적인 다이나믹 프로그래밍 문제입니다.
행렬의 0행부터 끝행까지 각 행에서 1가지 원소를 선택하고 원소의 총합이 최대가 되도록 만드는 문제입니다.
점화식은 다음과 같습니다.
- 　\(dp(i,j) = max(dp(i-1, k)) + land(i,j) (k = 0,1,2,3 and j \neq k)\)
반복문을 수행한 다음에 가장 마지막 행의 최대값이 점수의 최대값이 됩니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> dp;

int solution(vector<vector<int> > land)
{
	int answer = 0;
	int N = land.size();
	int M = 4;
	dp = vector<vector<int>>(N, vector<int>(M, 0));
	dp[0][0] = land[0][0];
	dp[0][1] = land[0][1];
	dp[0][2] = land[0][2];
	dp[0][3] = land[0][3];

	for (int i = 1; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (j == 0) {
				dp[i][j] += max(dp[i - 1][1], max(dp[i - 1][2], dp[i - 1][3])) + land[i][j];
			}
			else if (j == 1) {
				dp[i][j] += max(dp[i - 1][0], max(dp[i - 1][2], dp[i - 1][3])) + land[i][j];
			}
			else if (j == 2) {
				dp[i][j] += max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][3])) + land[i][j];
			}
			else if (j == 3) {
				dp[i][j] += max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2])) + land[i][j];
			}
		}
	}

	for (int i = 0; i < 4; ++i) {
		answer = max(answer, dp[N - 1][i]);
	}

	return answer;
}