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; }