読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

ProjectEuler Problem18 : Maximum path sum I

問題リンク:Problem 18 - Project Euler

問題概要:
問題でしめされている図の最大コストを求めろ

解法:
dp[i][j] := max( dp[i][j],list[i][j]+dp[i-1][j-1],list[i][j]+dp[i-1][j])

として最大値をもとめる
ここで,listとは図の値が入った2次配列である

コード:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int list[16][16] =
  {
    {75},
    {95,64},
    {17,47,82},
    {18,35,87,10},
    {20, 4,82,47,65},
    {19, 1,23,75,03,34},
    {88, 2,77,73,07,63,67},
    {99,65, 4,28,06,16,70,92},
    {41,41,26,56,83,40,80,70,33},
    {41,48,72,33,47,32,37,16,94,29},
    {53,71,44,65,25,43,91,52,97,51,14},
    {70,11,33,28,77,73,17,78,39,68,17,57},
    {91,71,52,38,17,14,91,43,58,50,27,29,48},
    {63,66, 4,68,89,53,67,30,73,16,69,87,40,31},
    { 4,62,98,27,23, 9,70,98,73,93,38,53,60, 4,23},
  };

int main()
{
  int dp[16][16];
  for(int i=0;i<16;i++)
    for(int j=0;j<16;j++)
      dp[i][j] = 0;

  dp[0][0] = list[0][0];

  int mex = 0;
  for(int i=1;i<16;i++)
    {
      for(int j=0;j<i+1;j++)
	{
	  if(i >= j-1 && j-1 >= 0)
	    dp[i][j] = max(dp[i][j],list[i][j]+dp[i-1][j-1]);
	  if(i >= j   && j   >= 0)
	    dp[i][j] = max(dp[i][j],list[i][j]+dp[i-1][j]);
	  if(i == 15)
	    mex = max(mex,dp[i][j]);
	}
    }
  cout << mex << endl;

  return 0;
}