java - 欧拉计划问题 18 无法到达最后一个元素

Question

我正在尝试使用这些算法解决欧拉计划问题 18，将第一行添加到第二行并确保我们找到更大的值 通过用新值替换原始值来对每个值进行调整。

我知道我的代码没有到达每行的最后一个元素，但我该如何解决？

(问题描述:求三角形从上到下的最大总数，每行取一个数，每次移动到相邻的一个数。)

尝试

public static void main(String args[])  {

    int number[][] = {
            {75},
            {95,64},
            {17,47,82},
            {18,35,87,10},
            {20,04,82,47,65},
            {19,01,23,75,03,34},
            {88,02,77,73,07,63,67},
            {99,65,04,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,04,68,89,53,67,30,73,16,69,87,40,31},
            {04,62,98,27,23,9,70,98,73,93,38,53,60,04,23}};

    for(int i = 1 ; i < number.length ; i++ ) 
        for(int j = 0 , k = 0 ; j <= i+1 ; k++,j++) {
        // k is the number of term in previous array
                if(k < number[i-1].length) {
                    
                    // if the first term 
                    if(k == 0) {
                        // if the the k is the only number in the array >(when i = 0)
                        if (number[i-1].length == 1)
                    
                // add it to down value
                            number[i][j] += number[i-1][k];
                        else {
                            //then if we have 2 k add the bigger k to down  value
                            if(number[i-1][k+1]  > number[i-1][k])
                            number[i][j] += number[i-1][k+1];
                            else
                            number[i][j] += number[i-1][k];
                        }
                    }
                    // if k in the mid
                else if( k > 0 && k < number[i-1].length - 1) {
                    //add the bigger value to down term
                    if (number[i-1][k] < number[i-1][k+1] && number[i-1][k] < number[i-1][k-1] )
                        number[i][j] += number[i-1][k];
                    else if( number[i-1][k+1] > number[i-1][k-1] )
                        number[i][j] += number[i-1][k+1];
                    else
                        number[i][j] += number[i-1][k-1];
                }
                else {
                    // if the we reach last k 
                    if(number[i-1][k] > number[i-1][k-1])
                        number[i][j] += number[i-1][k];
                    else
                        number[i][j] += number[i-1][k-1];
                }
        
                }
        }
        
        
    int x = 3;
    for(int i = 0 ; i < number[x].length ; i++ )
    System.out.print(number[x][i] + " ");
    

}

Answer 1

这里有一个与您的算法相关的提示:想象三角形是倒置的，尖端在底部，底部在顶部。考虑到此处的最佳路径，尽管在描述中有指示，但出于我们的目的，可以在任一方向上进行追踪。

我们从底部开始，知道其中一个单元格是最佳路径中的最后一个单元格。底行的每一对细胞只有一个父代。我们选择对中较大的一个并将其添加到上面的父项中。按照此过程从每一行到顶部。