динамическое програмирование помогите решить пожайлуста

[kiberv1]

помогите решить задачи пожайлуста
Дана шахматна доска NxM і число k. Потрібно порахувати кількість способів розміщення на цій дошці королів так, щоб вони не били один одного.

На шахматній дошці NxM потрібно підрахувати кількість способів розставити k коней так, щоб вони не били один одного.

Петрику необхідно замостити величезну вулицю плиткою. Він використовує плитку розміром 1*2 метри, і може класти її або вертикально, або горизонтально. Вулиця поділена на квадрати з стороною 1 метр, і для кожного квадрата відомо дві ціни: перша - скільки заплатять Петрику, якщо цей квадрат покрити горизонтальною плиткою, друга - скільки заплатять Петрику, якщо цей квадрат покрити вертикальною плиткою. Підкажіть Петрику скільки максимально грошей він зможе заробити на цій роботі. При цьому слід памятати, що вулицю слід покрити плиткою повністю, гарантується, що це можна зробити.

[Nilenbert]

Ну перевели бы на русский, разве это сложно:

Дана шахматная доска NxM и число k. Нужно посчитать количество способов размещения на этой доске королей так, чтобы они не били друг друга.

На шахматной доске NxM нужно подсчитать количество способов расставить k коней так, чтобы они не били друг друга.

Петеньке необходимо замостить огромную улицу плиткой. Он использует плитку размером 1 * 2 метра, и может класть ее или вертикально, либо горизонтально. Улица разделена на квадраты со стороной 1 метр, и для каждого квадрата известно две цены: первая - сколько заплатят Петеньке, если этот квадрат покрыть горизонтальной плиткой, вторая - сколько заплатят Петеньке, если этот квадрат покрыть вертикальной плиткой. Подскажите Петеньке, сколько максимально денег он сможет заработать на этой работе. При этом следует помнить, что улицу следует покрыть плиткой полностью, гарантируется, что это можно сделать.