7 задач динамического программирования (ДП) с решениями и пояснениями на Java

Введение

Динамическое программирование (ДП) — мощный подход в программировании, который решает проблемы путём разбиения их на более мелкие подпроблемы и последовательного решения их, сохраняя промежуточные результаты. Это повышает эффективность алгоритма, так как подпроблемы не приходится пересчитывать несколько раз.

В этой статье мы рассмотрим семь задач ДП с подробными решениями на Java и пояснениями для лучшего понимания.

1. Вычисление числа Фибоначчи

Эффективное решение на Java:

public class FibonacciDP {

    public static int fib(int n) {
        int[] dp = new int[n + 1];

        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i  nums[j]) {
                    max = Math.max(max, dp[j]);
                }
            }
            dp[i] = max + 1;
        }

        return dp[n - 1];
    }
}

Пояснение:

Создаём массив dp для хранения длин LIS, заканчивающихся каждым элементом nums.
Инициализируем первый элемент dp значением 1, так как LIS, заканчивающаяся первым элементом, имеет длину 1.
Разделяем задачу на подпроблемы и решаем их последовательно, сравнивая nums[i] с nums[j] для получения максимальной длины LIS, заканчивающейся nums[i].

3. Определение, можно ли получить определённую сумму набором монет

Эффективное решение на Java:

public class CoinChangeDP {

    public static boolean canGetSum(int[] coins, int sum) {
        boolean[] dp = new boolean[sum + 1];

        dp[0] = true;

        for (int i = 1; i = 0 && dp[i - coin]) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[sum];
    }
}

Пояснение:

Создаём массив dp, где dp[i] указывает, можно ли получить сумму i набором монет coins.
Инициализируем первый элемент dp значением true, поскольку пустым набором монет можно получить сумму 0.
Разделяем задачу на подпроблемы и решаем их последовательно, проверяя каждую монету для каждой суммы.

4. Вычисление минимального количества монет для получения определённой суммы

Эффективное решение на Java:

public class CoinChangeMinCoinsDP {

    public static int minCoins(int[] coins, int sum) {
        int[] dp = new int[sum + 1];

        for (int i = 1; i  a.distance - b.distance);
        pq.add(new Node(source, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            if (current.distance > distance[current.vertex]) {
                continue;
            }

            for (int neighbor : graph[current.vertex]) {
                int newDistance = current.distance + graph[current.vertex][neighbor];
                if (newDistance < distance[neighbor]) {
                    distance[neighbor] = newDistance;
                    pq.add(new Node(neighbor, newDistance));
                }
            }
        }

        return distance;
    }

    private static class Node {
        int vertex;
        int distance;

        Node(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
    }
}

Пояснение:

Используем алгоритм Дейкстры для нахождения минимальных путей от заданного источника до всех вершин в графе с весами рёбер.
Создаём массив distance, где distance[i] указывает на минимальное расстояние от источника до вершины i.
Инициализируем distance большими значениями, а расстояние от источника до себя самого устанавливаем в 0.
Используем очередь с приоритетом pq для эффективного выбора вершин для обработки.
При обработке вершины current обновляем distance для всех её соседей, если новый путь короче.

6. Нахождение кратчайшего общего суперпоследовательности (LCS)

Эффективное решение на Java:

public class LCSDP {

    public static int lcs(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i