Участник:Никита Плетнев/minimum score triangulation polygon

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/minimum-score-triangulation-of-polygon/submissions/

class Solution {
public:
    int minScoreTriangulation(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> dinamo(n, vector<int>(n, INT_MAX));
        for (int j = 1; j <= n; ++j) {
            for (int i = 0; i < n - j + 1; ++i) {
                int m = i + j - 1;
                if (j <= 2)
                    dinamo[i][m]=0;
                for (int k = i + 1; k < m; ++k) {
                    int possible = dinamo[i][k] + dinamo[k][m] + A[i] * A[k] * A[m];
                    if (possible < dinamo[i][m])
                        dinamo[i][m] = possible;
                }
            }
        }
        return dinamo[0][n-1];
    }
};