「プロジェクトオイラー問い81～90」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問い81～90 - (2013/01/03 (木) 02:25:25) のソース

*問い81
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2081
80*80サイズの表の左上から出発して表の右下まで進む時、経路上の数字の和が最小になるルートを求めよ。
下か右にしか移動できないものとする。

解法
一段ずつの動的計画法で一発です。

 #include<stdio.h>
 #include<string.h>
 int main(){
 	int ans[81][81],num;
 	char c;
 	memset(ans,0,sizeof(ans));
 	for(int i=1;i<=80;i++){
 		for(int j=1;j<=80;j++){
 			scanf("%d%c",&num,&c);
 			if(i==1){
 				ans[i][j]=num+ans[i][j-1];
 			}else if(j==1){
 				ans[i][j]=num+ans[i-1][j];
 			}else{
 				ans[i][j]=num+(ans[i-1][j]<ans[i][j-1]?ans[i-1][j]:ans[i][j-1]);
 			}
 		}
 	}
 	printf("%d",ans[80][80]);
 }