[Baekjoon/C++] 24418번: 알고리즘 수업 - 행렬 경로 문제 1(Dynamic Programming)

# Baekjoon 24418번: 알고리즘 수업 - 행렬 경로 문제 1

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

int rec = 0;
int dp = 0;
int matrix_path_rec(vector<vector<int>>& m, int i, int j);

int matrix_path(vector<vector<int>>& m, int n) {
	return matrix_path_rec(m, n, n);
}

int matrix_path_rec(vector<vector<int>>& m, int i, int j) {
	if (i == 0 or j == 0) {
		rec++;
		return 0;
	}
	else
		return m[i][j] + max(matrix_path_rec(m, i - 1, j), matrix_path_rec(m, i, j - 1));
}

int matrix_path_dp(vector<vector<int>>& m, int n) {
	for (int i = 0; i < n + 1; i++) m[i][0] = 0;
	for (int j = 1; j < n + 1; j++) m[0][j] = 0;

	for (int i = 1; i < n + 1; i++) {
		for (int j = 1; j < n + 1; j++) {
			m[i][j] = m[i][j] + max(m[i - 1][j], m[i][j - 1]);
			dp++;
		}
	}
	return m[n][n];
}

int main(void) {
	int n;
	cin >> n;
	vector<vector<int>> m(n + 1, vector<int>(n + 1));

	for (int i = 1; i < n + 1; i++) {
		for (int j = 1; j < n + 1; j++)
			cin >> m[i][j];
	}
	
	vector<vector<int>> m2 = m;

	matrix_path(m, n);
	matrix_path_dp(m2, n);

	cout << rec << " " << dp;

	return 0;
}