Основная идея динамического программирования состоит в том, чтобы разложить проблему, которая должна быть решена на несколько подпрограмм, сначала решает подпрограмм и сохранение решений этих подпроблемы. Если вам необходимо использовать решения этих подпрограмм в будущем при решении более крупных подпрограмм, вы можете напрямую извлечь эти вычисленные решения, чтобы избежать повторных операций. Решение для сохранения подпрограмм может быть заполнено в использовании метода формы, такого как сохранение в массиве.
Используйте практический пример, чтобы отразить алгоритмическую идею динамического программирования - проблема изменения монеты.
Описание вопроса:
Предположим, есть несколько монет, и есть неограниченные количества. Пожалуйста, узнайте минимальное количество монет, которые могут составить определенное количество изменений. Например, несколько типов монет составляют [1, 3, 5], минимальное количество монет со значением поверхности 2 составляет 2 (1, 1), минимальное количество монет со значением поверхности 4 составляет 2 (1, 3), а минимальное количество монет со значением поверхности 11 составляет 3 (5, 5, 1 или 5, 3, 3).
Анализ проблем:
Предположим, что различные наборы монет являются массивной монетой [0, ..., N-1]. Затем найдите минимальное количество монет со значением поверхности k, затем функция Count и монета монеты соответствует этому условию:
count (k) = min (count (k - coin [0]), ..., count (k - coin [n - 1])) + 1;
И предыдущая формула сохраняется только в том случае, если условие k - coin [i]> = 0 && k - coin [i] <k выполнено.
Потому что k- монета [i] <k, при расчете подсчета (k), счет (i) (i <- [0, k-1]) должен быть выполнен, поэтому здесь включает проблему возврата.
Таким образом, мы можем создать матрицу матрицы [k + 1] [coin.length + 1], чтобы матрица [0] [j] все инициализирована до 0 значений и сохранить минимальное количество монет со значением лица I в матрице [i] [coin.length].
И конкретный процесс заключается в следующем:
* k | Coin 1 3 5 Min * 0 0 0 0 0 0 * 1 1 0 0 1 * 2 2 0 2 * 3 3 1 0 3, 1 * 2 2 2 0 2, 2 * 5 3 3 1 3, 3, 1 * 6 2 2 2 2, 2, 2 * ...
Наконец, конкретная реализация кода Java заключается в следующем:
public static int BackTrackingCoin (int [] Coins, int k) {// Метод отступления + динамическое программирование if (coins == null || coins.length == 0 || k <1) {return 0; } int [] [] matrix = new int [k + 1] [coins.length + 1]; for (int i = 1; i <= k; i ++) {for (int j = 0; j <coins.length; j ++) {int prek = i - coins [j]; if (prek> -1) {// только тогда, когда это не менее 0, Prek может существовать в матрице массива, и может быть выполнено обратное отслеживание. Матрица [i] [j] = matrix [prek] [coins.length] + 1; // Значение лица i обрабатывает if (matrix [i] [coins.length] == 0 || matrix [i] [j] <matrix [i] [coins.length]) {// Если текущий номер числа сотовых сотовых. Матрица [i] [coins.length] = matrix [i] [j]; }}} вернуть матрицу [k] [coins.length]; }Код был протестирован, и все тестовые случаи, представленные по вопросу, прошли!
Суммировать
Выше приведено все содержание этой статьи о проблеме реализации проблемы с изменением монеты динамического программирования Java. Я надеюсь, что это будет полезно для всех. Заинтересованные друзья могут продолжать ссылаться на другие связанные темы на этом сайте. Если есть какие -либо недостатки, пожалуйста, оставьте сообщение, чтобы указать это. Спасибо, друзья, за вашу поддержку на этом сайте!