3 задачи по динамич.программир. на с#

1. На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной. Определить эту сумму.

2. В исследовательской лаборатории фирмы Robots&Co разработали новую модель робота. Главной особенностью данной модели робота является то, что он работает по заранее заданной программе, в которой могут присутствовать команды: сделать шаг на Юг, на Север, на Восток или на Запад. Робот исполняет программу строго последовательно и, дойдя до конца программы, останавливается. Специалисты из Robot&Co заинтересовались вопросом, сколько существует различных программ, состоящих из *K* инструкций, таких, что робот, выйдя из начала координат, придет в точку с координатами *(X, Y)*. Оси координат располагаются параллельно сторонам света, и единица измерения, соответствует одному шагу робота. Напишите программу, которая дает ответ на этот вопрос.

3. Давным-давно в далекой галактике... была планета Ялмез, третья планета по счеты от звезды Ецилос. На этой планете жили существа йормелы. Йормелы - очень добрые и миролюбивые существа. Над ними правил Дохуторас. Долгое время йормелы жили без войн... Но вот на йормелов напала другая раса. Этих существ звали кохиты. Предводителем этих существ был Понарас. Понарас, коварный и бесчестный, намерился захватить все города йормелов. Дохуторас решил дать отпор захватчикам и защитить свои *n* городов.

Дохуторас собрал армию численностью *k* (силой является количество слодат в армии). У йормелов есть необычное свойство: если количество йормелов (солдат) в городе кратно 2, то их сила увеличивается в 3 раза. Если сила проивников больше, чем сила йормелов, то йормелы сдают город противникам.

Понарас разделил свою армию на *n* частей и направил каждую часть армии в какой-либо город (две армии не могут идти в один город). Дохуторас поручил вам, великому полководству, распределить солдат так, чтобы йормелы защитили максимальное количество городов. Дохуторас может использовать не всех солдат своей армии.