c*u
发帖数: 22 | 1 三角数求最大和，如
By starting at the top of the triangle and moving to adjacent numbers on the
row below, the maximum total from top to bottom is 27
5
9 6
4 6 8
0 7 1 5
I.e. 5 + 9 + 6 + 7 = 27.
find the maximum total from top to bottom a text file containing a triangle
with 100 rows. |
g**G
发帖数: 767 | 2 maintain another array stores the max sum in current level
For example
5 5
9 6 14 11
4 6 8 18 20 19
0 7 1 5 18 27 21 24 |
c********p
发帖数: 1969 | 3 13 哪来的？13那个不对吧。。。
【在 g**G 的大作中提到】
: maintain another array stores the max sum in current level
: For example
: 5 5
: 9 6 14 11
: 4 6 8 18 20 19
: 0 7 1 5 18 27 21 24
|
r**d
发帖数: 316 | 4 从下往上算，一个简单的DP
0 7 1 5
11 13 13
22 19
27
the
triangle
【在 c*u 的大作中提到】
: 三角数求最大和，如
: By starting at the top of the triangle and moving to adjacent numbers on the
: row below, the maximum total from top to bottom is 27
: 5
: 9 6
: 4 6 8
: 0 7 1 5
: I.e. 5 + 9 + 6 + 7 = 27.
: find the maximum total from top to bottom a text file containing a triangle
: with 100 rows.
|
o******e
发帖数: 1001 | 5 怎么看不懂题目。
the
triangle
【在 c*u 的大作中提到】
: 三角数求最大和，如
: By starting at the top of the triangle and moving to adjacent numbers on the
: row below, the maximum total from top to bottom is 27
: 5
: 9 6
: 4 6 8
: 0 7 1 5
: I.e. 5 + 9 + 6 + 7 = 27.
: find the maximum total from top to bottom a text file containing a triangle
: with 100 rows.
|
g**G
发帖数: 767 | 6 en... fixed
【在 c********p 的大作中提到】
: 13 哪来的？13那个不对吧。。。
|
c********p
发帖数: 1969 | 7 yeah, it makes sense now.
it's a good way to do it. I used to do it from the butt.
【在 g**G 的大作中提到】
: en... fixed
|
J****3
发帖数: 427 | |
c*u
发帖数: 22 | 9 这样可以么？ list 保存每一轮数值并用变量记下该轮最大值：
从上往下
string filename = "data.txt";
if (File.Exists(filename))
{
string line;
List list = new List();
StreamReader sr = File.OpenText(filename);
int max = 0;
while ((line = sr.ReadLine()) != null)
{
int[] array = line.Trim().Split(' ').Select(n => int.Parse(n)).ToArray<
int>();
int size = array.Count();
if (size ==1)
{
list.Add( array[0]);
max = list[0];
}
else if (size>1)
{
int next=0, val = 0;
for (int i = 0; i < size-1 ; i++)
{
val = list[i];
if (i == 0)
list[i] = list[i] + array[i];
else
{
int mid = list[i] + array[i];
list[i] = (mid > next) ? mid : next;
}
max = (max>list[i])?max:list[i];
next = val + array[i + 1];
if (i == size - 2)
{
list.Add(next);
max = (max > next) ? max : next;
break;
}
}
}
}
Console.WriteLine(max);
sr.Close();
}
data.txt
5
9 6
4 6 8
0 7 1 5
【在 g**G 的大作中提到】
: maintain another array stores the max sum in current level
: For example
: 5 5
: 9 6 14 11
: 4 6 8 18 20 19
: 0 7 1 5 18 27 21 24
|
b******7
发帖数: 92 | 10 简单dp
sum(i, j) 自底向上到i层j元素的最大和，目标sum(0, 0)
sum(i, j) = A[i,j] + max{sum(i+1, j), sum(i+1, j+1)}
边界sum(n-1, j) = A[n-1, j]
the
triangle
【在 c*u 的大作中提到】
: 三角数求最大和，如
: By starting at the top of the triangle and moving to adjacent numbers on the
: row below, the maximum total from top to bottom is 27
: 5
: 9 6
: 4 6 8
: 0 7 1 5
: I.e. 5 + 9 + 6 + 7 = 27.
: find the maximum total from top to bottom a text file containing a triangle
: with 100 rows.
|
c*u
发帖数: 22 | 11 string filename = "data.txt";
if (File.Exists(filename))
{
int depth = 100;
int[,] arr = new int[depth,depth];
StreamReader sr = File.OpenText(filename);
int loop = 0;
while ((line = sr.ReadLine()) != null)
{
int[] array = line.Trim().Split(' ').Select(n => int.Parse(n)).
ToArray();
for(int i=0;i
arr[loop, i] = array[i];
Console.WriteLine(line);
loop++;
}
sr.Close();
//从最底下两层开始
for (loop = depth - 2; loop >= 0; loop --)
for (int j = 0; j <= loop; j++)
arr[loop, j] += Math.Max(arr[loop + 1, j], arr[loop + 1, j + 1]);
Console.WriteLine("The maximum path sum is: " + arr[0, 0]);
}
【在 c*u 的大作中提到】
: 这样可以么？ list 保存每一轮数值并用变量记下该轮最大值：
: 从上往下
: string filename = "data.txt";
: if (File.Exists(filename))
: {
: string line;
: List list = new List();
: StreamReader sr = File.OpenText(filename);
: int max = 0;
: while ((line = sr.ReadLine()) != null)
|
p*i
发帖数: 411 | 12 bottom-up
vector> num; // assume this is the input
const int n = num.size();
if (n == 0) return 0;
for (int i = n-2; i >= 0 --i) {
for (int j = 0; j <= i; ++j) {
num[i][j] += max(num[i+1][j], num[i+1][j+1]);
}
}
return num[0][0];
the
triangle
【在 c*u 的大作中提到】
: 三角数求最大和，如
: By starting at the top of the triangle and moving to adjacent numbers on the
: row below, the maximum total from top to bottom is 27
: 5
: 9 6
: 4 6 8
: 0 7 1 5
: I.e. 5 + 9 + 6 + 7 = 27.
: find the maximum total from top to bottom a text file containing a triangle
: with 100 rows.
|
k*******t
发帖数: 144 | 13 同感
【在 J****3 的大作中提到】
: leetcode triangle??
|
