Участник:Никита Плетнев/remove boxes

Материал из DISCOPAL
< Участник:Никита Плетнев
Версия от 23:13, 5 декабря 2020; Никита Плетнев (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://leetcode.com/problems/remove-boxes/submissions/

class Solution {
public:
    int dinamo[101][101][101];
 
    int subsolver(vector<int>& boxes, int left_bound, int right_bound, int count) {
        if (left_bound > right_bound) 
            return 0;
        if (dinamo[left_bound][right_bound][count] != -1) 
            return dinamo[left_bound][right_bound][count];
 
        int answer = (count + 1) * (count + 1) + subsolver(boxes, left_bound + 1, right_bound, 0);
 
        for (int i = left_bound + 1; i <= right_bound; ++i) {
            if (boxes[i] == boxes[left_bound]) {
                int possible = subsolver(boxes, left_bound + 1, i - 1, 0) + subsolver(boxes, i, right_bound, count + 1);
                if (possible > answer)
                    answer = possible;
            }
        }
        dinamo[left_bound][right_bound][count] = answer;
        return answer;
    }
 
    int removeBoxes(vector<int>& boxes) {
        int length = boxes.size();
        memset(dinamo, -1, sizeof(dinamo));
        return subsolver(boxes, 0, length - 1, 0);
    }
};