Тут для одной окружности пример на С дан

Ищите лучшие прагмы по хештегу #pragma

Описываешь эту фигуру аналитической функцией и складываешь элементы площади.

Есть задачи решаемые дп  и для них дп не лучший способ

А задач, для которых дп лучший способ нет?

считаешь ли ты задачу нахождения минимума в массиве дп? считаешь ли ты дп + что-то - дп?

Есть задача про башни, есть n башен, у каждой масса и прочность(сколько массы можно поставить), надо взять максимальное число башен, за квадрат она решается дп, за нлогн - сортировка + жадник

If we were able to say precisely what we mean by terms like greedy algorithms, dynamic programming, network flow algorithms, local-search,
etc., then, when confronted with a new problem, we could hope to either find an algorithm
for it by placing it in one of these models, or show that it doesn’t fit the model and move on to the next model.

Задача 2 яйца и сто этажей

Решается через дп

Но намного проще без

Или так

Сколько способов вернуть сдачу монетами? Дп даёт экспоненциально решение, а анал комбинаторика линейное.

Ребят, а у меня такая просьба. Можете помочь понять решение.

Есть строка, которая состоит из '(', ')', '*' и нужно определить валидная ли расстановка скобок. Звёздочки можно рассматривать как пустота, или открывающаяся скобка, или закрывающаяся.

(*)(      -> invalid
(()(**) -> valid
(*()))   -> valid


Решение такое.
Пройдемся по массиву с лева направо и на каждом шаге проверяем, валидная ли расстановка скобок, если считать каждую звёздочку как левую.
Потом справа на лево, проверяя на каждом шаге, валидная ли перестановка, если считать * как правая.

Если до этого мы не вернули false, то здесь возвращаем true. То есть что перестановка валидная.

Но я не могу понять последний шаг

То есть почему это значит, что существует такой выбор правых, левых, и пустых скобок для звёздочек, что исходная строка становится валидной?

(*** не очень понятен первый шаг алгоритма в таком случае

Если скобка левая или звёздочка, то counter++. Если правая, то counter--.  Если на каком-то шаге counter<0 return false

как counter может стать меньше нуля если только его увеличение присутствует?

Если правая, то counter--