Đề bài
Cho tam giác số vuông (right number triangle), tìm tổng lớn nhất của các số xuất hiện trên đường đi từ đỉnh đến đáy, sao cho mỗi bước số tiếp theo nằm ngay dưới hoặc dưới và sang phải một vị trí.
Ví dụ
Input: 3 4 5 1 10 7 Tổng lớn nhất = 18 (3 + 5 + 10).
Thuật toán
Ý tưởng: tìm tổng lớn nhất kết thúc tại mỗi ô của hàng cuối, trả về max của các tổng đó.
Có thể tính đệ quy bằng cách xét hai ô phía trên. Do có bài toán con chồng chéo, dùng quy hoạch động để tìm tổng lớn nhất kết thúc tại ô cụ thể của hàng cuối.
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 << "Tổng lớn nhất = " << maxSum(tringle, 3) << endl; return 0; }Kết quả
Tổng lớn nhất = 18