Добрый день. Я понимаю, что это выглядит как просьба сделать работу за меня, но не знаю, как разубедить :)
У меня есть задача - последовательность N чисел, и вопрос стоит так - сколько наименьшее число обменов элементов последовательности, которые надо сделать, чтобы она стала сортированной. Мне кажется, что ее можно решить динамическим программированием.
Как я понимаю, динамическое программирование - это разбиение задачи на подзадачу поменьше с использованием ее решения, но никак не могу сообразить, какую именно подзадачу я должен решить.
Если это подзадача - сколько обменов для N-1 элементов, так ведь очередной может быть таким, что придется всю последовательность перетасовать, чтоб его на место поставить? А как я понимаю, для любой последовательности больше N-1 обмена не потребуется? А тут может быть так, что для меньшей - N-2 обмена, и еще для этого элемента N-1 - значит, это не подходит?
Или как подзадачу брать расстановку последовательности без, скажем, наибольшего элемента? А потом как его на место поставить - просто последовательностью обменов до конца? Непохоже, потому что, может, было бы выгоднее убрать какой-то другой элемент?
Задача не учебная, придумал сам для себя, чтоб разобраться с ДП. Или я придумал ерунду и ДП для этой задачи вообще не применимо?
Словом, был бы благодарен за подталкивание на правильный путь.
И еще - по книжкам читая, кажется, что для каждой задачи авторы придумывают какой-то свой способ, и нет никакого общего принципа, как динамическое программирование применять. Если повезет - придумаешь, а не повезет - значит, никак? Неужели нет какого-то формального подхода?
[2,1]
, нужно получить[1,2]
, не на своих местах 2 элемента, но обмен нужен один – Grundy♦ 6 дек '16 в 12:33