[动态规划] 数字三角形问题（一维数组实现）

               7
             3   8
           8   1   0
         2   7   7   4
       5   5   2   6   5

/** 
 *  
 * @author Eric 
 * 
 */  
public class TriangleProblem {  
  
    /** 
     * 使用一维数组结合动态规划思想求解数字三角形问题。
     * @param array 存储三角形数字的一维数组(从上到下，从左到右存储) 
     * @param n 数字三角形的行数 
     * @return 返回一个经过路径的数字的总和最大值 
     */  
    public int populateMaxSum(int[] array, int n) {  
        int[] result = new int[array.length];  
          
        for (int row = 0; row < n; row++) {  
            if (row == 0) {  
                /* 
                 * 设置定点的值  
                 */  
                result[0] = array[0];  
            } else {  
                int rowStartIndex = populateStartRowIndex(row);  
                  
                /* 
                 * 设置第row行第一个位置到顶点的最大值只有一个。
                 * 直接赋值。
                 */  
                result[rowStartIndex] = array[rowStartIndex]  
                        + result[rowStartIndex - row];  
  
                for (int col = 1; col <= row; col++) {  
                      
                    if (col < row) {  
                        /* 
                         * 处理到顶点的数值有两个节点的位置， 
                         * 取大的那一个。
                         */  
                        result[rowStartIndex + col] = max(result[rowStartIndex  
                                - row + col - 1]  
                                + array[rowStartIndex + col],  
                                array[rowStartIndex + col]  
                                        + result[rowStartIndex - row + col]);  
                    } else {  
                          
                        /* 
                         * 每行最右边的的位置到顶点的最大值也只有一个。
                         * 此时 row == col 
                         * 直接赋值。
                         */  
                        result[rowStartIndex + col] = result[rowStartIndex  
                                - row + col - 1]  
                                + array[rowStartIndex + col];  
                    }  
  
                }  
            }  
        }  
        /* 
         * 当所有的位置到顶点的位置都计算出来之后， 
         * 要计算出最大值，只要计算最大行中最大值即可。
         *  
         */  
        return max(populateStartRowIndex(n - 1), result);  
    }  
  
    /** 
     * 根据一个指定的行号，计算出在一维数组中对应的下标，最为该行的起始下标 
     * @param row 行号(从0开始) 
     * @return 
     */  
    private int populateStartRowIndex(int row) {  
        int sum = 0;  
        for (int i = 0; i <= row; i++) {  
            sum += i;  
        }  
        return sum;  
    }  
  
    private int max(int startIndex, int[] array) {  
        int max = array[startIndex];  
  
        for (int i = startIndex; i < array.length; i++) {  
            if (array[i] > max) {  
                max = array[i];  
            }  
  
        }  
        return max;  
    }  
  
    private int max(int v1, int v2) {  
        return (v1 > v2) ? v1 : v2;  
    }  
}

public class Main {  
  
    public static void main(String[] args) {  
        TriangleProblem tp = new TriangleProblem();  
        int[] array = { 7, 3, 8, 8, 1, 0, 2, 7, 4, 4, 4, 5, 2, 6, 5 };  
        System.out.printf("最大和为 SUM=%d", tp.populateMaxSum(array, 5));  
    }  
}

最大和为 SUM=30

7
3 8
8 1 0
2 7 7 4
5 5 2 6 5
... ...