三角形-题解（Java代码）

解题思路:

注意事项:

参考代码:

//递归(乌龟版)
    public static int number(int result[][],int row,int cloumn) {
        if (row == result.length-1) {//递归出口
            return result[row][cloumn];
        }
        int current = result[row][cloumn];//记录根节点
        int left = number(result,row+1,cloumn);//记录根节点的左下
        int right = number(result,row+1,cloumn+1);//记录根节点的右下
        return current+Math.max(left, right);//取最大值
    }
    
    //动态规划(循环)
    public static int numberOne(int result[][]) {
        /*
         * 思路：求总路径的最优解，可以先求每一个小路径的最优解，每一个最优解都进行合并。一直合并到三角形的最顶层
         * 
         * 状态：result(0,0)是路径最优解
         * 状态转换方程：result(i,j) = Math.max(result(i+1,j)+result(i,j),result(i+1,j+1)+result(i,j))
         * 边界：细节决定边界，不能取最后一行，如果取了最后一行存在数组越界
         */
        
        for (int i = result.length-2; i > -1; i--) {
            for (int j = 0; j <= i; j++) {
                result[i][j] = Math.max(result[i+1][j]+result[i][j], result[i+1][j+1]+result[i][j]);
            }
        }
        return result[0][0];
    }