Brute-force дает O(n^3) а жадность получается O(n^2)?

О(n)

Подскажите, пожалуйста, как написать код для такого задания?

У меня есть две функции : a(x,y) - складывает числа х и y, m(x,y) - умножает х и у. Изначально есть две константы: 0 и 1. Допустим, если я хочу получить число 2, то я могу сделать a(1,1) и это будет мне стоить 6 символов. Для числа 4 = m(a(1,1),a(1,1)) цена 16 символов. Как через минимальное количество символов вывести любое число?(в частности мне нужно 708)

Ну вроде динамикой решается

Это тест от компании Hudson River Trading?

))

greedy algorithm

Нет, от другой, но с Codility.

Вроде, там решение за O(n) - complexity, O(1) - memory

Greedy для меня новая тема, так что пока не понимаю как получится O(n) если там три части

что-то мне подсказывает, что использование константы 0 ваще ничего не даст и надо использовать только единицу

Я не уверен, что там greedy, но подумай в направлении того, сколько 'a' должно быть в каждой части.
Отталкиваясь от этого, сколько есть способов расставить границы так, чтобы получить это количество 'a' в каждой из трёх частей.

второй момент - если мы можем сказать, что 708 = какому-то арифметическому выражению, то мы можем построить дерево этого выражения. В каждом узле операция * или +, а все листья это числа 1. Можно пересчитать старую стоимость как число листьев + 4*число не-листьев

ну и дальше надо придумать какие-то способы оптимизации такого дерева. А именно операции по сокращению числа узлов.

взять некоторого "тривиальное" решение (например сумму степеней двойки) и потом оптимизировать его

Да динамика же

/me не знает, что это такое

Aragaer не знает, что это тако

Arina

Да, действительно. Greedy не нужен: считаем сколько возможно с начала, считаем сколько возможно с конца.
Результаты перемножаем. Это и есть ответ.