The Triangle - POJ 1163 - Virtual Judge

题目大意

在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。

路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。

三角形的行数大于1小于等于100，数字为 0 - 99

输入格式：

5 //表示三角形的行数 接下来输入三角形

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

要求输出最大和

代码

三种写法 dp 滚动dp 递归

package BlueCup.Eight_DP_greed;

import java.util.Scanner;

import static java.lang.Math.max;

public class 数字三角形 {
    //改问题不是贪心，不能通过上一步决定下一步
    static int n;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        int[][] triangel = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                triangel[i][j] = cin.nextInt();
            }
        }
        int ans = dp(triangel);
        System.out.println(ans);
        ans=dpOne(triangel);
        System.out.println(ans);
    }


    /**
     * DP
     * -位置在变 分析依赖 先求什么后求什么
     * 所以我们从最后一行开始解决问题 maxLine-i
     * @param triangel
     * @return
     */
    private static int dp(int[][] triangel) {
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[n - 1][i] = triangel[n - 1][i];//最后一行
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = triangel[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }
        return dp[0][0];
    }

    /**
     *滚动数组DP 节约空间
     * 把dp压缩为一维
     *注意 dp是 i的索引
     */
    private static int dpOne(int[][] triangel) {
        int dp[] = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = triangel[n - 1][i];//最后一行
        }
        for (int i = n - 2; i>=0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j]=triangel[i][j]+max(dp[j],dp[j+1]);
            }
        }
        return dp[0];
    }

    /**
     * 递归解法
     * @param i
     * @param j
     * @param triangel
     * @return
     */
    private static int maxAns(int i, int j, int[][] triangel) {
        if (i == n - 1) {//到达最后一行
            return triangel[i][j];
        } else {//定点的数值 +左侧 右侧 的最大值
            return triangel[i][j] + max(maxAns(i + 1, j + 1, triangel), maxAns(i + 1, j, triangel));
        }
    }
}