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 (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/Algorithm/258.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。