sudocode.js

let input = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
let y = 4;
let x = 3;

function init3d(x, y) {
	let dp = new Array(y);
	for (let i = 0; i < y; i++ ) {
		dp[i] = new Array(x + 2);
		for (let j = 0; j < x + 2; j++ ) {
			dp[i][j] = new Array(x + 2);
			for (let k = 0; k < x + 2; k++ ) {
				dp[i][j][k] = 0;
			}
		}
	}
	return dp
}

function solution (input, x ,y) {
 	let dp = init3d(x, y); // x 양끝에 bound 늘려주기
	dp[0][1][ x ] = input[0][0] + input[0][x - 1];
	let answer = -99999999;

	for (let i = 1; i < y; i++) {
		for (let j = 1; j <= x; j++ ) {
			for (let k = 1; k <= x; k++ ) {
				let w = input[i][j - 1];
				if (j !== k ) w += input[i][k - 1];

				let prev = Math.max(dp[i - 1][j - 1][k - 1], Math.max(dp[i - 1][j - 1][k], dp[i - 1][j + 1][k + 1]));
				prev = Math.max(prev, Math.max(dp[i - 1][j][k - 1], Math.max(dp[i - 1][j][k], dp[i - 1][j][k + 1])));
				prev = Math.max(prev, Math.max(dp[i - 1][j + 1][k - 1], Math.max(dp[i - 1][j + 1][k], dp[i - 1][j + 1][k + 1])));
				dp[i][j][k] = prev + w;
				answer = Math.max(answer , dp[i][j][k]);
			
			}
  		}
  	}
    return answer;
}

console.log(solution(input,x, y));