algospot_DIAMONDPATH_solution

DP_algospot.cpp

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

// DP solution
int solve (vector< vector<int> > &grid){
	// edge case
	int m=grid.size(), n=grid[0].size();
	int DP[101][101] = {0,};

	// copy the grid into the DP table
	for (int i=0; i < m; i++){
		for (int j=0; j < n; j++){
			DP[i+1][j+1] = grid[i][j];
		}
	}

	// DP process
	for (int i=1; i <= m; i++)
		for (int j=1; j <= n; j++)
			DP[i][j] += max(DP[i-1][j-1] , DP[i-1][j]);

	return DP[m-1][n-1];
}

int main()
{
	int n;
	cin >> n;
	vector< vector<int> > grid;
	int t;

	// convert matrix
	// 5
	// 6
	// 1 2
	// 6 7 4
	// 9 4 1 7
	// 6 7 5 9 4
	// 4 4 3 2
	// 1 2 3
	// 6 1
	// 7

	for (int i=0; i < 2*n-1; i++){
		vector<int> row;
		int j;
		for (j=0; j<n; j++){
			if ((i >= n && j <= i-n) || (i < n && j > i))
				row.push_back(0);
			else{
				cin >> t;
				row.push_back(t);
			}
		}
		grid.push_back(row);
	}

	// into 
	// 6 0 0 0 0
	// 1 2 0 0 0
	// 6 7 4 0 0
	// 9 4 1 7 0
	// 6 7 5 9 4
	// 0 4 4 3 2
	// 0 0 1 2 3
	// 0 0 0 6 1
	// 0 0 0 0 7   

	// print the matrix for debugging
	for (int i=0; i < grid.size(); i++){
		for (int j=0; j < grid[0].size(); j++)
			cout << grid[i][j] << " ";
		cout << endl;
	}
	cout << solve(grid);
}