Tam giác trong C ++

Giả sử chúng ta có một tam giác. Chúng ta phải tìm tổng đường đi tối thiểu từ trên xuống dưới. Trong mỗi bước, chúng ta có thể di chuyển đến các số liền kề trên hàng bên dưới.

Ví dụ:nếu hình tam giác sau đây giống như

[
      [2],
     [3,4],
    [6,5,7],
   [4,1,8,3]
]

Tổng đường dẫn tối thiểu từ trên xuống dưới là 11 (2 + 3 + 5 + 1 =11).

Hãy để chúng tôi xem các bước -

• Tạo một bảng để sử dụng trong phương pháp tiếp cận Lập trình động.

• n:=kích thước của tam giác

• for i:=n - 2 xuống 0

  • for j:=0 to i

    • dp [j]:=tam giác [i, j] + tối thiểu của dp [j] và dp [j + 1]

• trả về dp [0]

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minimumTotal(vector<vector<int>>& triangle) {
      vector <int> dp(triangle.back());
      int n = triangle.size();
      for(int i = n - 2; i >= 0; i--){
         for(int j = 0; j <= i; j++){
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
         }
      }
      return dp[0];
   }
};
main(){
   Solution ob;
   vector<vector<int> > v = {{2},{3,4},{6,5,7},{4,1,8,3}};
   cout << ob.minimumTotal(v);
}

Đầu vào

[
      [2],
     [3,4],
    [6,5,7],
   [4,1,8,3]
]

Đầu ra

11