寒光博客

[LanQiao] 数字三角形 The Triangle 动态规划
The Triangle - POJ 1163 - Virtual Judge 题目大意 在数字三角形中寻找一条从...
扫描右侧二维码阅读全文
20
2019/08

[LanQiao] 数字三角形 The Triangle 动态规划

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));
        }
    }
}
本文作者:Author:     文章标题:[LanQiao] 数字三角形 The Triangle 动态规划
本文地址:https://dxoca.cn/Algorithm/258.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:September 2nd, 2019 at 11:38 am
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment