AOJの問題で、質問があります。
AOJの問題で考えても全然わからない問題があり、他の人の解答例を参考にしようと思い、見てみたのですが、一つ分からないところがあり、質問させていただきます。
問題です。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0089
自分が参考にしている解答例です。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=570672
以下は分かっていないところを書かせていただきます。
なお、コードは解答例と同じです。
include <stdio.h>
#include <string.h>
int max(int a,int b){
return (a > b) ? a : b;
}
/*上の数、i-1行目の数から、i行目の大きい数をとっていく関数だと思いましたが、じっくり考えてみると、何パターンかのdataの足し算をしていることに気づきました。まずは左端のみ足す場（data[i+1][0] += data[i][0];）、次に右端だけを足す場合（ data[i+1][i+1] += data[i][i];） 、そして
for(j = 1;j <= i;j++){
data[i+1][j] += max(data[i][j-1],data[i][j]);
}
という、端以外の数から足すものです。ここで分からないことは
・このdata[i+1][j] += max(data[i][j-1],data[i][j]);という解答はi+1行目から、i行目の大きな数を選んでいますが、i行目からi+1行目の隣の大きいほうの数を足すようにしないと、ただしい経路は求まらないと思うのですが、どうでしょうか？また、端のみを足しているdataは、どういう役割をしているのでしょうか？ 試しに端だけを足す式を削除したら、間違いとなってしまいます。また、この関数はreturn などがないですが、どの値が残るのでしょうか？main関数内では、どのような役割をするのでしょうか？*/
void solve(int data[100][50],int cnt){
int i,j;
for(i = 0;i < cnt/2;i++){
data[i+1][0] += data[i][0];
for(j = 1;j <= i;j++){
data[i+1][j] += max(data[i][j-1],data[i][j]);
}
data[i+1][i+1] += data[i][i];
}
for(i = cnt/2+1;i < cnt;i++){
for(j = 0;j < cnt-i;j++){
data[i][j] += max(data[i-1][j],data[i-1][j+1]);
}
}
}
int main(){
int h,i,j,cnt,len,num;
int data[100][50];
char str[1024];
memset(data,0,sizeof(data));
i = 0;
cnt = 0;
while(scanf("%s",str) != EOF){
h = 0;
j = 0;
len = strlen(str);
while(h <= len){
if(h < len && str[h] != ','){
num = 0;
while(h < len && str[h] != ','){
num *= 10;
num += str[h]-'0';
h++;
}
data[i][j] = num;
j++;
}
h++;
}
i++;
cnt++;
}
solve(data,cnt);//ここでは、計算した結果、どのような値が帰ってくるのでしょうか？
printf("%d\n",data[cnt-1][0]);
return 0;
}
長文失礼しました。
よろしくお願いします。
![その他([技術者向] コンピューター) イメージ](https://gazo.okwave.jp/okwave/spn/images/related_qa/c205_4_thumbnail_img_sm.png)
