Tổng tối đa của một đường dẫn trong Tam giác số bên phải trong C ++

Tuyên bố vấn đề

Cho một tam giác vuông gồm các số, hãy tìm tổng số lớn nhất xuất hiện trên các đường dẫn bắt đầu từ đỉnh về phía gốc, sao cho trên mỗi đường dẫn, số tiếp theo nằm ngay bên dưới hoặc bên dưới-và-một-nơi-đến -phải

Ví dụ

If given input is:
3
4 5
1 10 7
Then maximum sum is 18 as (3 + 5 + 10).

Thuật toán

Ý tưởng là tìm tổng lớn nhất kết thúc tại mỗi ô của hàng cuối cùng và trả về số tiền tối đa trong số các tổng này.

Chúng ta có thể tính toán đệ quy các tổng này bằng cách xem xét đệ quy hai ô trên

Vì có các vấn đề con chồng chéo, chúng tôi sử dụng lập trình động để tìm tổng lớn nhất kết thúc tại ô cụ thể của hàng cuối cùng

Ví dụ

#include<bits/stdc++.h>
using namespace std;
int maxSum(int tringle[][3], int n){
   if (n > 1) {
      tringle[1][1] = tringle[1][1] + tringle[0][0];
      tringle[1][0] = tringle[1][0] + tringle[0][0];
   }
   for(int i = 2; i < n; i++) {
      tringle[i][0] = tringle[i][0] + tringle[i-1][0];
      tringle[i][i] = tringle[i][i] + tringle[i-1][i-1];
      for (int j = 1; j < i; j++){
         if (tringle[i][j] + tringle[i-1][j-1] >=tringle[i][j] + tringle[i-1][j]) {
            tringle[i][j] = tringle[i][j] + tringle[i-1][j-1];
         } else {
            tringle[i][j] = tringle[i][j]+tringle[i-1][j];
         }
      }
   }
   int max = tringle[n - 1][0];
   for(int i = 1;i < n; i++) {
      if(max < tringle[n-1][i]) {
         max=tringle[n-1][i];
      }
   }
   return max;
}
int main(){
   int tringle[3][3] = {
      {3},
      {4,5},
      {1,10,7}
   };
   cout << "Maximum sum = " << maxSum(tringle, 3) << endl;
   return 0;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra tiếp theo -

Maximum sum = 18