Smallest sum in a triangle, c++.

[xypher]

hi! i've been trying to solve this problem for the past couple of hours but i dont have any ideas. i need to find the smallest sum from the top of a triangle down to the bottom and write the sum and the path. could you guys help me?

[Nineshadow]

Can you be more specific?

Anyway, backtracking is always an option. Maybe not the most efficient one, but it is a solution.

[xypher]

Can you be more specific?

Anyway, backtracking is always an option. Maybe not the most efficient one, but it is a solution.

ok so,    

     4

   1 4

  9 9 3

 9 4 4 3

4 5 2 5 6  this is an example.. so i need to find the path that has the smallest sum from top to bottom. i dont really know how to explain it in english

[Nineshadow]

 

ok so,    

4

   1 4

  9 9 3

 9 4 4 3

4 5 2 5 6 

Cred ca m-am prins.

Imi dai si un exemplu? Sau ala e unu' ?

[xypher]

Cred ca m-am prins.

Imi dai si un exemplu? Sau ala e unu' ?

 

Cred ca m-am prins.

Imi dai si un exemplu? Sau ala e unu' ?

17

4 4 3 4 2 asta trebuie sa afiseze (am uitat sa pun si asta in comentariu de mai sus)

[madknight3]

Given the following triangle

  1   6 89 4 1

The solution is

1 8 1 = 10

Two ways you can approach this problem are

1. Bottom up
2. Top down

I'll describe one possible way to get the answer using a bottom-up approach. Basically, you'll want to add the result from the previous row to the next row using the minimum. Then you're left with the answer.

 

Here's an example of the bottom up approach

// Starting with this  1   6 89 4 1// You'll start by taking the min of the first pair (9 and 4) and adding it to the item above (6)// Then you repeat for every pair in that row// Once the first set of calculations are done you'll be left with this  1  10 9// Because// min(9, 4) = 4 and 4 + 6 = 10// min(4, 1) = 1 and 1 + 8 = 9// Then you repeat for every row.// In this example after one more row you are left with your answer  10// Because// min(10, 9) = 9 and 9 + 1 = 10

There are other ways to solve this problem, but this is the way I first figured it out on my own many years ago.

 

Hopefully this will help you get started. How you decide to implement it in code will be up to you to attempt. I want to help but I don't want to write it for you.

[xypher]

Given the following triangle

  1   6 89 4 1

The solution is

1 8 1 = 10

Two ways you can approach this problem are

1. Bottom up
2. Top down

I'll describe one possible way to get the answer using a bottom-up approach. Basically, you'll want to add the result from the previous row to the next row using the minimum. Then you're left with the answer.

 

Here's an example of the bottom up approach

// Starting with this  1   6 89 4 1// You'll start by taking the min of the first pair (9 and 4) and adding it to the item above (6)// Then you repeat for every pair in that row// Once the first set of calculations are done you'll be left with this  1  10 9// Because// min(9, 4) = 4 and 4 + 6 = 10// min(4, 1) = 1 and 1 + 8 = 9// Then you repeat for every row.// In this example after one more row you are left with your answer  10// Because// min(10, 9) = 9 and 9 + 1 = 10

There are other ways to solve this problem, but this is the way I first figured it out on my own many years ago.

 

Hopefully this will help you get started. How you decide to implement it in code will be up to you to attempt. I want to help but I don't want to write it for you.

Thanks for the idea!