Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 14.5 Задача о полном рюкзаке

В этом разделе сначала решим еще одну распространенную задачу о рюкзаке - задачу о полном рюкзаке, а затем рассмотрим один из ее типичных частных случаев: задачу о размене монет.

## 14.5.1 Задача о полном рюкзаке

Question

Даны \(n\) предметов. Вес \(i\)-го предмета равен \(wgt[i-1]\) , стоимость равна \(val[i-1]\) . Также дан рюкзак вместимости \(cap\) . Каждый предмет можно выбирать многократно. Найдите максимальную суммарную стоимость, которую можно поместить в рюкзак при заданной вместимости. Пример показан на рисунке 14-22.

Рисунок 14-22 Пример данных для задачи о полном рюкзаке

### 1. Идея динамического программирования

Задача о полном рюкзаке очень похожа на задачу о рюкзаке 0-1. Разница состоит только в том, что количество выборов каждого предмета не ограничено.

- В задаче о рюкзаке 0-1 каждого предмета существует только один экземпляр, поэтому после того как предмет \(i\) помещен в рюкзак, выбирать можно только из первых \(i-1\) предметов.
- В задаче о полном рюкзаке количество предметов не ограничено, поэтому после того как предмет \(i\) помещен в рюкзак, можно продолжать выбирать из первых \(i\) предметов.

При этом состояние \([i, c]\) в задаче о полном рюкзаке может изменяться двумя способами.

- Не брать предмет \(i\) : как и в задаче о рюкзаке 0-1, переход осуществляется в \([i-1, c]\) .
- Взять предмет \(i\) : в отличие от рюкзака 0-1 переход происходит в \([i, c-wgt[i-1]]\) .

Следовательно, уравнение перехода состояния принимает вид:

\[ dp[i, c] = \max(dp[i-1, c], dp[i, c - wgt[i-1]] + val[i-1]) \]

### 2. Реализация кода

Если сравнить код этой задачи с кодом задачи о рюкзаке 0-1, то окажется, что в переходе состояний меняется только одна деталь: вместо \(i-1\) появляется \(i\). Все остальное остается таким же:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
unbounded_knapsack.py

    def unbounded_knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
        """Полный рюкзак: динамическое программирование"""
        n = len(wgt)
        # Инициализация таблицы dp
        dp = [[0] * (cap + 1) for _ in range(n + 1)]
        # Переход состояний
        for i in range(1, n + 1):
            for c in range(1, cap + 1):
                if wgt[i - 1] > c:
                    # Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c]
                else:
                    # Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1])
        return dp[n][cap]

unbounded_knapsack.cpp

    /* Полный рюкзак: динамическое программирование */
    int unboundedKnapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
        int n = wgt.size();
        // Инициализация таблицы dp
        vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[n][cap];
    }

unbounded_knapsack.java

    /* Полный рюкзак: динамическое программирование */
    int unboundedKnapsackDP(int[] wgt, int[] val, int cap) {
        int n = wgt.length;
        // Инициализация таблицы dp
        int[][] dp = new int[n + 1][cap + 1];
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[n][cap];
    }

unbounded_knapsack.cs

    /* Полный рюкзак: динамическое программирование */
    int UnboundedKnapsackDP(int[] wgt, int[] val, int cap) {
        int n = wgt.Length;
        // Инициализация таблицы dp
        int[,] dp = new int[n + 1, cap + 1];
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i, c] = dp[i - 1, c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i, c] = Math.Max(dp[i - 1, c], dp[i, c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[n, cap];
    }

unbounded_knapsack.go

    /* Полный рюкзак: динамическое программирование */
    func unboundedKnapsackDP(wgt, val []int, cap int) int {
        n := len(wgt)
        // Инициализация таблицы dp
        dp := make([][]int, n+1)
        for i := 0; i <= n; i++ {
            dp[i] = make([]int, cap+1)
        }
        // Переход состояний
        for i := 1; i <= n; i++ {
            for c := 1; c <= cap; c++ {
                if wgt[i-1] > c {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i-1][c]
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = int(math.Max(float64(dp[i-1][c]), float64(dp[i][c-wgt[i-1]]+val[i-1])))
                }
            }
        }
        return dp[n][cap]
    }

unbounded_knapsack.swift

    /* Полный рюкзак: динамическое программирование */
    func unboundedKnapsackDP(wgt: [Int], val: [Int], cap: Int) -> Int {
        let n = wgt.count
        // Инициализация таблицы dp
        var dp = Array(repeating: Array(repeating: 0, count: cap + 1), count: n + 1)
        // Переход состояний
        for i in 1 ... n {
            for c in 1 ... cap {
                if wgt[i - 1] > c {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c]
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1])
                }
            }
        }
        return dp[n][cap]
    }

unbounded_knapsack.js

    /* Полный рюкзак: динамическое программирование */
    function unboundedKnapsackDP(wgt, val, cap) {
        const n = wgt.length;
        // Инициализация таблицы dp
        const dp = Array.from({ length: n + 1 }, () =>
            Array.from({ length: cap + 1 }, () => 0)
        );
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            for (let c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = Math.max(
                        dp[i - 1][c],
                        dp[i][c - wgt[i - 1]] + val[i - 1]
                    );
                }
            }
        }
        return dp[n][cap];
    }

unbounded_knapsack.ts

    /* Полный рюкзак: динамическое программирование */
    function unboundedKnapsackDP(
        wgt: Array<number>,
        val: Array<number>,
        cap: number
    ): number {
        const n = wgt.length;
        // Инициализация таблицы dp
        const dp = Array.from({ length: n + 1 }, () =>
            Array.from({ length: cap + 1 }, () => 0)
        );
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            for (let c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = Math.max(
                        dp[i - 1][c],
                        dp[i][c - wgt[i - 1]] + val[i - 1]
                    );
                }
            }
        }
        return dp[n][cap];
    }

unbounded_knapsack.dart

    /* Полный рюкзак: динамическое программирование */
    int unboundedKnapsackDP(List<int> wgt, List<int> val, int cap) {
      int n = wgt.length;
      // Инициализация таблицы dp
      List<List<int>> dp = List.generate(n + 1, (index) => List.filled(cap + 1, 0));
      // Переход состояний
      for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
          if (wgt[i - 1] > c) {
            // Если вместимость рюкзака превышена, предмет i не выбирать
            dp[i][c] = dp[i - 1][c];
          } else {
            // Большее из двух решений: не брать или взять предмет i
            dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
          }
        }
      }
      return dp[n][cap];
    }

unbounded_knapsack.rs

    /* Полный рюкзак: динамическое программирование */
    fn unbounded_knapsack_dp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
        let n = wgt.len();
        // Инициализация таблицы dp
        let mut dp = vec![vec![0; cap + 1]; n + 1];
        // Переход состояний
        for i in 1..=n {
            for c in 1..=cap {
                if wgt[i - 1] > c as i32 {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = std::cmp::max(dp[i - 1][c], dp[i][c - wgt[i - 1] as usize] + val[i - 1]);
                }
            }
        }
        return dp[n][cap];
    }

unbounded_knapsack.c

    /* Полный рюкзак: динамическое программирование */
    int unboundedKnapsackDP(int wgt[], int val[], int cap, int wgtSize) {
        int n = wgtSize;
        // Инициализация таблицы dp
        int **dp = malloc((n + 1) * sizeof(int *));
        for (int i = 0; i <= n; i++) {
            dp[i] = calloc(cap + 1, sizeof(int));
        }
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = myMax(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        int res = dp[n][cap];
        // Освободить память
        for (int i = 0; i <= n; i++) {
            free(dp[i]);
        }
        return res;
    }

unbounded_knapsack.kt

    /* Полный рюкзак: динамическое программирование */
    fun unboundedKnapsackDP(wgt: IntArray, _val: IntArray, cap: Int): Int {
        val n = wgt.size
        // Инициализация таблицы dp
        val dp = Array(n + 1) { IntArray(cap + 1) }
        // Переход состояний
        for (i in 1..n) {
            for (c in 1..cap) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c]
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + _val[i - 1])
                }
            }
        }
        return dp[n][cap]
    }

unbounded_knapsack.rb

    ### Полный рюкзак: динамическое программирование ###
    def unbounded_knapsack_dp(wgt, val, cap)
      n = wgt.length
      # Инициализация таблицы dp
      dp = Array.new(n + 1) { Array.new(cap + 1, 0) }
      # Переход состояний
      for i in 1...(n + 1)
        for c in 1...(cap + 1)
          if wgt[i - 1] > c
            # Если вместимость рюкзака превышена, предмет i не выбирать
            dp[i][c] = dp[i - 1][c]
          else
            # Большее из двух решений: не брать или взять предмет i
            dp[i][c] = [dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]].max
          end
        end
      end
      dp[n][cap]
    end

Визуализация кода

Во весь экран >

### 3. Оптимизация пространства

Поскольку текущее состояние переходит из состояния слева и состояния сверху, после оптимизации памяти каждую строку таблицы \(dp\) нужно обходить слева направо.

Этот порядок обхода как раз противоположен задаче о рюкзаке 0-1. Эту разницу удобно понять, рассмотрев то, что показано на рисунке 14-23.

<1><2><3><4><5><6>

Рисунок 14-23 Процесс динамического программирования после оптимизации памяти для полного рюкзака

Код реализации здесь довольно прост: достаточно просто убрать первое измерение массива `dp` :

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
unbounded_knapsack.py

    def unbounded_knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
        """Полный рюкзак: динамическое программирование с оптимизацией памяти"""
        n = len(wgt)
        # Инициализация таблицы dp
        dp = [0] * (cap + 1)
        # Переход состояний
        for i in range(1, n + 1):
            # Прямой обход
            for c in range(1, cap + 1):
                if wgt[i - 1] > c:
                    # Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c]
                else:
                    # Большее из двух решений: не брать или взять предмет i
                    dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
        return dp[cap]

unbounded_knapsack.cpp

    /* Полный рюкзак: динамическое программирование с оптимизацией памяти */
    int unboundedKnapsackDPComp(vector<int> &wgt, vector<int> &val, int cap) {
        int n = wgt.size();
        // Инициализация таблицы dp
        vector<int> dp(cap + 1, 0);
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[cap];
    }

unbounded_knapsack.java

    /* Полный рюкзак: динамическое программирование с оптимизацией памяти */
    int unboundedKnapsackDPComp(int[] wgt, int[] val, int cap) {
        int n = wgt.length;
        // Инициализация таблицы dp
        int[] dp = new int[cap + 1];
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[cap];
    }

unbounded_knapsack.cs

    /* Полный рюкзак: динамическое программирование с оптимизацией памяти */
    int UnboundedKnapsackDPComp(int[] wgt, int[] val, int cap) {
        int n = wgt.Length;
        // Инициализация таблицы dp
        int[] dp = new int[cap + 1];
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = Math.Max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[cap];
    }

unbounded_knapsack.go

    /* Полный рюкзак: динамическое программирование с оптимизацией памяти */
    func unboundedKnapsackDPComp(wgt, val []int, cap int) int {
        n := len(wgt)
        // Инициализация таблицы dp
        dp := make([]int, cap+1)
        // Переход состояний
        for i := 1; i <= n; i++ {
            for c := 1; c <= cap; c++ {
                if wgt[i-1] > c {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c]
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = int(math.Max(float64(dp[c]), float64(dp[c-wgt[i-1]]+val[i-1])))
                }
            }
        }
        return dp[cap]
    }

unbounded_knapsack.swift

    /* Полный рюкзак: динамическое программирование с оптимизацией памяти */
    func unboundedKnapsackDPComp(wgt: [Int], val: [Int], cap: Int) -> Int {
        let n = wgt.count
        // Инициализация таблицы dp
        var dp = Array(repeating: 0, count: cap + 1)
        // Переход состояний
        for i in 1 ... n {
            for c in 1 ... cap {
                if wgt[i - 1] > c {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c]
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
                }
            }
        }
        return dp[cap]
    }

unbounded_knapsack.js

    /* Полный рюкзак: динамическое программирование с оптимизацией памяти */
    function unboundedKnapsackDPComp(wgt, val, cap) {
        const n = wgt.length;
        // Инициализация таблицы dp
        const dp = Array.from({ length: cap + 1 }, () => 0);
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            for (let c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[cap];
    }

unbounded_knapsack.ts

    /* Полный рюкзак: динамическое программирование с оптимизацией памяти */
    function unboundedKnapsackDPComp(
        wgt: Array<number>,
        val: Array<number>,
        cap: number
    ): number {
        const n = wgt.length;
        // Инициализация таблицы dp
        const dp = Array.from({ length: cap + 1 }, () => 0);
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            for (let c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[cap];
    }

unbounded_knapsack.dart

    /* Полный рюкзак: динамическое программирование с оптимизацией памяти */
    int unboundedKnapsackDPComp(List<int> wgt, List<int> val, int cap) {
      int n = wgt.length;
      // Инициализация таблицы dp
      List<int> dp = List.filled(cap + 1, 0);
      // Переход состояний
      for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
          if (wgt[i - 1] > c) {
            // Если вместимость рюкзака превышена, предмет i не выбирать
            dp[c] = dp[c];
          } else {
            // Большее из двух решений: не брать или взять предмет i
            dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
          }
        }
      }
      return dp[cap];
    }

unbounded_knapsack.rs

    /* Полный рюкзак: динамическое программирование с оптимизацией памяти */
    fn unbounded_knapsack_dp_comp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
        let n = wgt.len();
        // Инициализация таблицы dp
        let mut dp = vec![0; cap + 1];
        // Переход состояний
        for i in 1..=n {
            for c in 1..=cap {
                if wgt[i - 1] > c as i32 {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = std::cmp::max(dp[c], dp[c - wgt[i - 1] as usize] + val[i - 1]);
                }
            }
        }
        dp[cap]
    }

unbounded_knapsack.c

    /* Полный рюкзак: динамическое программирование с оптимизацией памяти */
    int unboundedKnapsackDPComp(int wgt[], int val[], int cap, int wgtSize) {
        int n = wgtSize;
        // Инициализация таблицы dp
        int *dp = calloc(cap + 1, sizeof(int));
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = myMax(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        int res = dp[cap];
        // Освободить память
        free(dp);
        return res;
    }

unbounded_knapsack.kt

    /* Полный рюкзак: динамическое программирование с оптимизацией памяти */
    fun unboundedKnapsackDPComp(
        wgt: IntArray,
        _val: IntArray,
        cap: Int
    ): Int {
        val n = wgt.size
        // Инициализация таблицы dp
        val dp = IntArray(cap + 1)
        // Переход состояний
        for (i in 1..n) {
            for (c in 1..cap) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c]
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = max(dp[c], dp[c - wgt[i - 1]] + _val[i - 1])
                }
            }
        }
        return dp[cap]
    }

unbounded_knapsack.rb

    ### Полный рюкзак: динамическое программирование ###
    def unbounded_knapsack_dp(wgt, val, cap)
      n = wgt.length
      # Инициализация таблицы dp
      dp = Array.new(n + 1) { Array.new(cap + 1, 0) }
      # Переход состояний
      for i in 1...(n + 1)
        for c in 1...(cap + 1)
          if wgt[i - 1] > c
            # Если вместимость рюкзака превышена, предмет i не выбирать
            dp[i][c] = dp[i - 1][c]
          else
            # Большее из двух решений: не брать или взять предмет i
            dp[i][c] = [dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]].max
          end
        end
      end
      dp[n][cap]
    end

    # ## Полный рюкзак: динамическое программирование с оптимизацией памяти ##3
    def unbounded_knapsack_dp_comp(wgt, val, cap)
      n = wgt.length
      # Инициализация таблицы dp
      dp = Array.new(cap + 1, 0)
      # Переход состояний
      for i in 1...(n + 1)
        # Прямой обход
        for c in 1...(cap + 1)
          if wgt[i -1] > c
            # Если вместимость рюкзака превышена, предмет i не выбирать
            dp[c] = dp[c]
          else
            # Большее из двух решений: не брать или взять предмет i
            dp[c] = [dp[c], dp[c - wgt[i - 1]] + val[i - 1]].max
          end
        end
      end
      dp[cap]
    end

Визуализация кода

Во весь экран >

## 14.5.2 Задача о размене монет

Задача о рюкзаке представляет собой целый класс задач динамического программирования, у которого есть множество вариантов, и одной из таких вариаций является задача о размене монет.

Question

Даны \(n\) видов монет, номинал монеты \(i\) равен \(coins[i - 1]\) , а целевая сумма равна \(amt\) . Монеты каждого вида можно брать многократно. Требуется найти минимальное число монет, которыми можно набрать целевую сумму. Если набрать сумму невозможно, верните \(-1\) . Пример показан на рисунке 14-24.

Рисунок 14-24 Пример данных для задачи о размене монет

### 1. Идея динамического программирования

Задачу о размене монет можно рассматривать как частный случай задачи о полном рюкзаке. Между ними существуют следующие соответствия и различия.

- Эти две задачи можно взаимно преобразовать: «предмет» соответствует «монете», «вес предмета» соответствует «номиналу монеты», а «вместимость рюкзака» соответствует «целевой сумме».
- Цель оптимизации противоположна: в задаче о полном рюкзаке нужно максимизировать стоимость предметов, а в задаче о размене монет - минимизировать число монет.
- В задаче о полном рюкзаке ищется решение, не превышающее вместимость, а в задаче о размене монет требуется ровно набрать целевую сумму.

Шаг 1: продумать решения на каждом раунде, определить состояние и тем самым получить таблицу \(dp\)

Подзадача, соответствующая состоянию \([i, a]\) , выглядит так: минимальное число монет из первых \(i\) видов, которыми можно набрать сумму \(a\). Решение этой подзадачи обозначается как \(dp[i, a]\) .

Размер двумерной таблицы \(dp\) равен \((n+1) \times (amt+1)\) .

Шаг 2: найти оптимальную подструктуру и на ее основе вывести уравнение перехода состояния

По сравнению с задачей о полном рюкзаке здесь есть два отличия в уравнении перехода состояния.

- Нужно искать минимум, а не максимум, поэтому оператор \(\max()\) заменяется на \(\min()\) .
- Оптимизируемое значение - это число монет, а не суммарная стоимость, поэтому при выборе монеты нужно просто прибавить \(1\) .

\[ dp[i, a] = \min(dp[i-1, a], dp[i, a - coins[i-1]] + 1) \]

Шаг 3: определить граничные условия и порядок переходов

Когда целевая сумма равна \(0\) , минимальное число монет для ее набора равно \(0\) , то есть весь первый столбец \(dp[i, 0]\) заполняется нулями.

Когда монет нет, невозможно набрать никакую целевую сумму \(> 0\). Это и есть недопустимое решение. Чтобы функция \(\min()\) в уравнении перехода состояния могла распознавать и отбрасывать такие недопустимые решения, удобно использовать значение \(+ \infty\). То есть всю первую строку \(dp[0, a]\) нужно инициализировать значением \(+ \infty\) .

### 2. Реализация кода

Большинство языков программирования не предоставляет представление для \(+ \infty\) в целочисленном виде, поэтому обычно приходится заменять его на максимальное значение типа `int` . Но тогда возникает риск переполнения: операция \(+ 1\) в уравнении перехода может переполнить большое число.

Поэтому здесь мы используем число \(amt + 1\) как обозначение недопустимого решения, потому что для набора суммы \(amt\) максимум нужно не больше чем \(amt\) монет. Перед возвратом результата проверяем, равно ли \(dp[n, amt]\) значению \(amt + 1\). Если да, то возвращаем \(-1\) , что означает невозможность набрать целевую сумму. Код приведен ниже:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
coin_change.py

    def coin_change_dp(coins: list[int], amt: int) -> int:
        """Размен монет: динамическое программирование"""
        n = len(coins)
        MAX = amt + 1
        # Инициализация таблицы dp
        dp = [[0] * (amt + 1) for _ in range(n + 1)]
        # Переход состояний: первая строка и первый столбец
        for a in range(1, amt + 1):
            dp[0][a] = MAX
        # Переход состояний: остальные строки и столбцы
        for i in range(1, n + 1):
            for a in range(1, amt + 1):
                if coins[i - 1] > a:
                    # Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a]
                else:
                    # Меньшее из двух решений: не брать или взять монету i
                    dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
        return dp[n][amt] if dp[n][amt] != MAX else -1

coin_change.cpp

    /* Размен монет: динамическое программирование */
    int coinChangeDP(vector<int> &coins, int amt) {
        int n = coins.size();
        int MAX = amt + 1;
        // Инициализация таблицы dp
        vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
        // Переход состояний: первая строка и первый столбец
        for (int a = 1; a <= amt; a++) {
            dp[0][a] = MAX;
        }
        // Переход состояний: остальные строки и столбцы
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
                }
            }
        }
        return dp[n][amt] != MAX ? dp[n][amt] : -1;
    }

coin_change.java

    /* Размен монет: динамическое программирование */
    int coinChangeDP(int[] coins, int amt) {
        int n = coins.length;
        int MAX = amt + 1;
        // Инициализация таблицы dp
        int[][] dp = new int[n + 1][amt + 1];
        // Переход состояний: первая строка и первый столбец
        for (int a = 1; a <= amt; a++) {
            dp[0][a] = MAX;
        }
        // Переход состояний: остальные строки и столбцы
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
                }
            }
        }
        return dp[n][amt] != MAX ? dp[n][amt] : -1;
    }

coin_change.cs

    /* Размен монет: динамическое программирование */
    int CoinChangeDP(int[] coins, int amt) {
        int n = coins.Length;
        int MAX = amt + 1;
        // Инициализация таблицы dp
        int[,] dp = new int[n + 1, amt + 1];
        // Переход состояний: первая строка и первый столбец
        for (int a = 1; a <= amt; a++) {
            dp[0, a] = MAX;
        }
        // Переход состояний: остальные строки и столбцы
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i, a] = dp[i - 1, a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[i, a] = Math.Min(dp[i - 1, a], dp[i, a - coins[i - 1]] + 1);
                }
            }
        }
        return dp[n, amt] != MAX ? dp[n, amt] : -1;
    }

coin_change.go

    /* Размен монет: динамическое программирование */
    func coinChangeDP(coins []int, amt int) int {
        n := len(coins)
        max := amt + 1
        // Инициализация таблицы dp
        dp := make([][]int, n+1)
        for i := 0; i <= n; i++ {
            dp[i] = make([]int, amt+1)
        }
        // Переход состояний: первая строка и первый столбец
        for a := 1; a <= amt; a++ {
            dp[0][a] = max
        }
        // Переход состояний: остальные строки и столбцы
        for i := 1; i <= n; i++ {
            for a := 1; a <= amt; a++ {
                if coins[i-1] > a {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i-1][a]
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[i][a] = int(math.Min(float64(dp[i-1][a]), float64(dp[i][a-coins[i-1]]+1)))
                }
            }
        }
        if dp[n][amt] != max {
            return dp[n][amt]
        }
        return -1
    }

coin_change.swift

    /* Размен монет: динамическое программирование */
    func coinChangeDP(coins: [Int], amt: Int) -> Int {
        let n = coins.count
        let MAX = amt + 1
        // Инициализация таблицы dp
        var dp = Array(repeating: Array(repeating: 0, count: amt + 1), count: n + 1)
        // Переход состояний: первая строка и первый столбец
        for a in 1 ... amt {
            dp[0][a] = MAX
        }
        // Переход состояний: остальные строки и столбцы
        for i in 1 ... n {
            for a in 1 ... amt {
                if coins[i - 1] > a {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a]
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
                }
            }
        }
        return dp[n][amt] != MAX ? dp[n][amt] : -1
    }

coin_change.js

    /* Размен монет: динамическое программирование */
    function coinChangeDP(coins, amt) {
        const n = coins.length;
        const MAX = amt + 1;
        // Инициализация таблицы dp
        const dp = Array.from({ length: n + 1 }, () =>
            Array.from({ length: amt + 1 }, () => 0)
        );
        // Переход состояний: первая строка и первый столбец
        for (let a = 1; a <= amt; a++) {
            dp[0][a] = MAX;
        }
        // Переход состояний: остальные строки и столбцы
        for (let i = 1; i <= n; i++) {
            for (let a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
                }
            }
        }
        return dp[n][amt] !== MAX ? dp[n][amt] : -1;
    }

coin_change.ts

    /* Размен монет: динамическое программирование */
    function coinChangeDP(coins: Array<number>, amt: number): number {
        const n = coins.length;
        const MAX = amt + 1;
        // Инициализация таблицы dp
        const dp = Array.from({ length: n + 1 }, () =>
            Array.from({ length: amt + 1 }, () => 0)
        );
        // Переход состояний: первая строка и первый столбец
        for (let a = 1; a <= amt; a++) {
            dp[0][a] = MAX;
        }
        // Переход состояний: остальные строки и столбцы
        for (let i = 1; i <= n; i++) {
            for (let a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
                }
            }
        }
        return dp[n][amt] !== MAX ? dp[n][amt] : -1;
    }

coin_change.dart

    /* Размен монет: динамическое программирование */
    int coinChangeDP(List<int> coins, int amt) {
      int n = coins.length;
      int MAX = amt + 1;
      // Инициализация таблицы dp
      List<List<int>> dp = List.generate(n + 1, (index) => List.filled(amt + 1, 0));
      // Переход состояний: первая строка и первый столбец
      for (int a = 1; a <= amt; a++) {
        dp[0][a] = MAX;
      }
      // Переход состояний: остальные строки и столбцы
      for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
          if (coins[i - 1] > a) {
            // Если целевая сумма превышена, монету i не выбирать
            dp[i][a] = dp[i - 1][a];
          } else {
            // Меньшее из двух решений: не брать или взять монету i
            dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
          }
        }
      }
      return dp[n][amt] != MAX ? dp[n][amt] : -1;
    }

coin_change.rs

    /* Размен монет: динамическое программирование */
    fn coin_change_dp(coins: &[i32], amt: usize) -> i32 {
        let n = coins.len();
        let max = amt + 1;
        // Инициализация таблицы dp
        let mut dp = vec![vec![0; amt + 1]; n + 1];
        // Переход состояний: первая строка и первый столбец
        for a in 1..=amt {
            dp[0][a] = max;
        }
        // Переход состояний: остальные строки и столбцы
        for i in 1..=n {
            for a in 1..=amt {
                if coins[i - 1] > a as i32 {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[i][a] = std::cmp::min(dp[i - 1][a], dp[i][a - coins[i - 1] as usize] + 1);
                }
            }
        }
        if dp[n][amt] != max {
            return dp[n][amt] as i32;
        } else {
            -1
        }
    }

coin_change.c

    /* Размен монет: динамическое программирование */
    int coinChangeDP(int coins[], int amt, int coinsSize) {
        int n = coinsSize;
        int MAX = amt + 1;
        // Инициализация таблицы dp
        int **dp = malloc((n + 1) * sizeof(int *));
        for (int i = 0; i <= n; i++) {
            dp[i] = calloc(amt + 1, sizeof(int));
        }
        // Переход состояний: первая строка и первый столбец
        for (int a = 1; a <= amt; a++) {
            dp[0][a] = MAX;
        }
        // Переход состояний: остальные строки и столбцы
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[i][a] = myMin(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
                }
            }
        }
        int res = dp[n][amt] != MAX ? dp[n][amt] : -1;
        // Освободить память
        for (int i = 0; i <= n; i++) {
            free(dp[i]);
        }
        free(dp);
        return res;
    }

coin_change.kt

    /* Размен монет: динамическое программирование */
    fun coinChangeDP(coins: IntArray, amt: Int): Int {
        val n = coins.size
        val MAX = amt + 1
        // Инициализация таблицы dp
        val dp = Array(n + 1) { IntArray(amt + 1) }
        // Переход состояний: первая строка и первый столбец
        for (a in 1..amt) {
            dp[0][a] = MAX
        }
        // Переход состояний: остальные строки и столбцы
        for (i in 1..n) {
            for (a in 1..amt) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a]
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
                }
            }
        }
        return if (dp[n][amt] != MAX) dp[n][amt] else -1
    }

coin_change.rb

    ### Размен монет: динамическое программирование ###
    def coin_change_dp(coins, amt)
      n = coins.length
      _MAX = amt + 1
      # Инициализация таблицы dp
      dp = Array.new(n + 1) { Array.new(amt + 1, 0) }
      # Переход состояний: первая строка и первый столбец
      (1...(amt + 1)).each { |a| dp[0][a] = _MAX }
      # Переход состояний: остальные строки и столбцы
      for i in 1...(n + 1)
        for a in 1...(amt + 1)
          if coins[i - 1] > a
            # Если целевая сумма превышена, монету i не выбирать
            dp[i][a] = dp[i - 1][a]
          else
            # Меньшее из двух решений: не брать или взять монету i
            dp[i][a] = [dp[i - 1][a], dp[i][a - coins[i - 1]] + 1].min
          end
        end
      end
      dp[n][amt] != _MAX ? dp[n][amt] : -1
    end

Визуализация кода

Во весь экран >

Как показано на рисунке 14-25, процесс динамического программирования для задачи о размене монет очень похож на задачу о полном рюкзаке.

<1><2><3><4><5><6><7><8><9><10><11><12><13><14><15>

Рисунок 14-25 Процесс динамического программирования для задачи о размене монет

### 3. Оптимизация пространства

Оптимизация пространства для задачи о размене монет выполняется так же, как и для полного рюкзака:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
coin_change.py

    def coin_change_dp_comp(coins: list[int], amt: int) -> int:
        """Размен монет: динамическое программирование с оптимизацией памяти"""
        n = len(coins)
        MAX = amt + 1
        # Инициализация таблицы dp
        dp = [MAX] * (amt + 1)
        dp[0] = 0
        # Переход состояний
        for i in range(1, n + 1):
            # Прямой обход
            for a in range(1, amt + 1):
                if coins[i - 1] > a:
                    # Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a]
                else:
                    # Меньшее из двух решений: не брать или взять монету i
                    dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
        return dp[amt] if dp[amt] != MAX else -1

coin_change.cpp

    /* Размен монет: динамическое программирование с оптимизацией памяти */
    int coinChangeDPComp(vector<int> &coins, int amt) {
        int n = coins.size();
        int MAX = amt + 1;
        // Инициализация таблицы dp
        vector<int> dp(amt + 1, MAX);
        dp[0] = 0;
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
                }
            }
        }
        return dp[amt] != MAX ? dp[amt] : -1;
    }

coin_change.java

    /* Размен монет: динамическое программирование с оптимизацией памяти */
    int coinChangeDPComp(int[] coins, int amt) {
        int n = coins.length;
        int MAX = amt + 1;
        // Инициализация таблицы dp
        int[] dp = new int[amt + 1];
        Arrays.fill(dp, MAX);
        dp[0] = 0;
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
                }
            }
        }
        return dp[amt] != MAX ? dp[amt] : -1;
    }

coin_change.cs

    /* Размен монет: динамическое программирование с оптимизацией памяти */
    int CoinChangeDPComp(int[] coins, int amt) {
        int n = coins.Length;
        int MAX = amt + 1;
        // Инициализация таблицы dp
        int[] dp = new int[amt + 1];
        Array.Fill(dp, MAX);
        dp[0] = 0;
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[a] = Math.Min(dp[a], dp[a - coins[i - 1]] + 1);
                }
            }
        }
        return dp[amt] != MAX ? dp[amt] : -1;
    }

coin_change.go

    /* Размен монет: динамическое программирование */
    func coinChangeDPComp(coins []int, amt int) int {
        n := len(coins)
        max := amt + 1
        // Инициализация таблицы dp
        dp := make([]int, amt+1)
        for i := 1; i <= amt; i++ {
            dp[i] = max
        }
        // Переход состояний
        for i := 1; i <= n; i++ {
            // Прямой обход
            for a := 1; a <= amt; a++ {
                if coins[i-1] > a {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a]
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[a] = int(math.Min(float64(dp[a]), float64(dp[a-coins[i-1]]+1)))
                }
            }
        }
        if dp[amt] != max {
            return dp[amt]
        }
        return -1
    }

coin_change.swift

    /* Размен монет: динамическое программирование с оптимизацией памяти */
    func coinChangeDPComp(coins: [Int], amt: Int) -> Int {
        let n = coins.count
        let MAX = amt + 1
        // Инициализация таблицы dp
        var dp = Array(repeating: MAX, count: amt + 1)
        dp[0] = 0
        // Переход состояний
        for i in 1 ... n {
            for a in 1 ... amt {
                if coins[i - 1] > a {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a]
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
                }
            }
        }
        return dp[amt] != MAX ? dp[amt] : -1
    }

coin_change.js

    /* Размен монет: динамическое программирование с оптимизацией памяти */
    function coinChangeDPComp(coins, amt) {
        const n = coins.length;
        const MAX = amt + 1;
        // Инициализация таблицы dp
        const dp = Array.from({ length: amt + 1 }, () => MAX);
        dp[0] = 0;
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            for (let a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
                }
            }
        }
        return dp[amt] !== MAX ? dp[amt] : -1;
    }

coin_change.ts

    /* Размен монет: динамическое программирование с оптимизацией памяти */
    function coinChangeDPComp(coins: Array<number>, amt: number): number {
        const n = coins.length;
        const MAX = amt + 1;
        // Инициализация таблицы dp
        const dp = Array.from({ length: amt + 1 }, () => MAX);
        dp[0] = 0;
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            for (let a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
                }
            }
        }
        return dp[amt] !== MAX ? dp[amt] : -1;
    }

coin_change.dart

    /* Размен монет: динамическое программирование с оптимизацией памяти */
    int coinChangeDPComp(List<int> coins, int amt) {
      int n = coins.length;
      int MAX = amt + 1;
      // Инициализация таблицы dp
      List<int> dp = List.filled(amt + 1, MAX);
      dp[0] = 0;
      // Переход состояний
      for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
          if (coins[i - 1] > a) {
            // Если целевая сумма превышена, монету i не выбирать
            dp[a] = dp[a];
          } else {
            // Меньшее из двух решений: не брать или взять монету i
            dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
          }
        }
      }
      return dp[amt] != MAX ? dp[amt] : -1;
    }

coin_change.rs

    /* Размен монет: динамическое программирование с оптимизацией памяти */
    fn coin_change_dp_comp(coins: &[i32], amt: usize) -> i32 {
        let n = coins.len();
        let max = amt + 1;
        // Инициализация таблицы dp
        let mut dp = vec![0; amt + 1];
        dp.fill(max);
        dp[0] = 0;
        // Переход состояний
        for i in 1..=n {
            for a in 1..=amt {
                if coins[i - 1] > a as i32 {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[a] = std::cmp::min(dp[a], dp[a - coins[i - 1] as usize] + 1);
                }
            }
        }
        if dp[amt] != max {
            return dp[amt] as i32;
        } else {
            -1
        }
    }

coin_change.c

    /* Размен монет: динамическое программирование с оптимизацией памяти */
    int coinChangeDPComp(int coins[], int amt, int coinsSize) {
        int n = coinsSize;
        int MAX = amt + 1;
        // Инициализация таблицы dp
        int *dp = malloc((amt + 1) * sizeof(int));
        for (int j = 1; j <= amt; j++) {
            dp[j] = MAX;
        }
        dp[0] = 0;

        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[a] = myMin(dp[a], dp[a - coins[i - 1]] + 1);
                }
            }
        }
        int res = dp[amt] != MAX ? dp[amt] : -1;
        // Освободить память
        free(dp);
        return res;
    }

coin_change.kt

    /* Размен монет: динамическое программирование с оптимизацией памяти */
    fun coinChangeDPComp(coins: IntArray, amt: Int): Int {
        val n = coins.size
        val MAX = amt + 1
        // Инициализация таблицы dp
        val dp = IntArray(amt + 1)
        dp.fill(MAX)
        dp[0] = 0
        // Переход состояний
        for (i in 1..n) {
            for (a in 1..amt) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a]
                } else {
                    // Меньшее из двух решений: не брать или взять монету i
                    dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
                }
            }
        }
        return if (dp[amt] != MAX) dp[amt] else -1
    }

coin_change.rb

    ### Размен монет: динамическое программирование с оптимизацией памяти ###
    def coin_change_dp_comp(coins, amt)
      n = coins.length
      _MAX = amt + 1
      # Инициализация таблицы dp
      dp = Array.new(amt + 1, _MAX)
      dp[0] = 0
      # Переход состояний
      for i in 1...(n + 1)
        # Прямой обход
        for a in 1...(amt + 1)
          if coins[i - 1] > a
            # Если целевая сумма превышена, монету i не выбирать
            dp[a] = dp[a]
          else
            # Меньшее из двух решений: не брать или взять монету i
            dp[a] = [dp[a], dp[a - coins[i - 1]] + 1].min
          end
        end
      end
      dp[amt] != _MAX ? dp[amt] : -1
    end

Визуализация кода

Во весь экран >

## 14.5.3 Задача о размене монет II

Question

Даны \(n\) видов монет, номинал монеты \(i\) равен \(coins[i - 1]\) , а целевая сумма равна \(amt\) . Монеты каждого вида можно брать многократно. Найдите число различных комбинаций монет, которыми можно набрать целевую сумму. Пример показан на рисунке 14-26.

Рисунок 14-26 Пример данных для задачи о размене монет II

### 1. Идея динамического программирования

По сравнению с предыдущей задачей здесь целью является число комбинаций. Поэтому подзадача меняется на следующую: число комбинаций из первых \(i\) видов монет, которыми можно набрать сумму \(a\). При этом таблица \(dp\) по-прежнему остается двумерной матрицей размера \((n+1) \times (amt + 1)\) .

Число комбинаций для текущего состояния равно сумме числа комбинаций для двух решений: не брать текущую монету и брать текущую монету. Поэтому уравнение перехода состояния принимает вид:

\[ dp[i, a] = dp[i-1, a] + dp[i, a - coins[i-1]] \]

Когда целевая сумма равна \(0\) , ее можно набрать, не выбирая ни одной монеты, поэтому весь первый столбец \(dp[i, 0]\) нужно инициализировать единицами. Когда монет нет, невозможно набрать никакую сумму \(>0\) , поэтому вся первая строка \(dp[0, a]\) должна быть заполнена нулями.

### 2. Реализация кода

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
coin_change_ii.py

    def coin_change_ii_dp(coins: list[int], amt: int) -> int:
        """Размен монет II: динамическое программирование"""
        n = len(coins)
        # Инициализация таблицы dp
        dp = [[0] * (amt + 1) for _ in range(n + 1)]
        # Инициализация первого столбца
        for i in range(n + 1):
            dp[i][0] = 1
        # Переход состояний
        for i in range(1, n + 1):
            for a in range(1, amt + 1):
                if coins[i - 1] > a:
                    # Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a]
                else:
                    # Сумма двух решений: не брать или взять монету i
                    dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
        return dp[n][amt]

coin_change_ii.cpp

    /* Размен монет II: динамическое программирование */
    int coinChangeIIDP(vector<int> &coins, int amt) {
        int n = coins.size();
        // Инициализация таблицы dp
        vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
        // Инициализация первого столбца
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
                }
            }
        }
        return dp[n][amt];
    }

coin_change_ii.java

    /* Размен монет II: динамическое программирование */
    int coinChangeIIDP(int[] coins, int amt) {
        int n = coins.length;
        // Инициализация таблицы dp
        int[][] dp = new int[n + 1][amt + 1];
        // Инициализация первого столбца
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
                }
            }
        }
        return dp[n][amt];
    }

coin_change_ii.cs

    /* Размен монет II: динамическое программирование */
    int CoinChangeIIDP(int[] coins, int amt) {
        int n = coins.Length;
        // Инициализация таблицы dp
        int[,] dp = new int[n + 1, amt + 1];
        // Инициализация первого столбца
        for (int i = 0; i <= n; i++) {
            dp[i, 0] = 1;
        }
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i, a] = dp[i - 1, a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[i, a] = dp[i - 1, a] + dp[i, a - coins[i - 1]];
                }
            }
        }
        return dp[n, amt];
    }

coin_change_ii.go

    /* Размен монет II: динамическое программирование */
    func coinChangeIIDP(coins []int, amt int) int {
        n := len(coins)
        // Инициализация таблицы dp
        dp := make([][]int, n+1)
        for i := 0; i <= n; i++ {
            dp[i] = make([]int, amt+1)
        }
        // Инициализация первого столбца
        for i := 0; i <= n; i++ {
            dp[i][0] = 1
        }
        // Переход состояний: остальные строки и столбцы
        for i := 1; i <= n; i++ {
            for a := 1; a <= amt; a++ {
                if coins[i-1] > a {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i-1][a]
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[i][a] = dp[i-1][a] + dp[i][a-coins[i-1]]
                }
            }
        }
        return dp[n][amt]
    }

coin_change_ii.swift

    /* Размен монет II: динамическое программирование */
    func coinChangeIIDP(coins: [Int], amt: Int) -> Int {
        let n = coins.count
        // Инициализация таблицы dp
        var dp = Array(repeating: Array(repeating: 0, count: amt + 1), count: n + 1)
        // Инициализация первого столбца
        for i in 0 ... n {
            dp[i][0] = 1
        }
        // Переход состояний
        for i in 1 ... n {
            for a in 1 ... amt {
                if coins[i - 1] > a {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a]
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
                }
            }
        }
        return dp[n][amt]
    }

coin_change_ii.js

    /* Размен монет II: динамическое программирование */
    function coinChangeIIDP(coins, amt) {
        const n = coins.length;
        // Инициализация таблицы dp
        const dp = Array.from({ length: n + 1 }, () =>
            Array.from({ length: amt + 1 }, () => 0)
        );
        // Инициализация первого столбца
        for (let i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            for (let a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
                }
            }
        }
        return dp[n][amt];
    }

coin_change_ii.ts

    /* Размен монет II: динамическое программирование */
    function coinChangeIIDP(coins: Array<number>, amt: number): number {
        const n = coins.length;
        // Инициализация таблицы dp
        const dp = Array.from({ length: n + 1 }, () =>
            Array.from({ length: amt + 1 }, () => 0)
        );
        // Инициализация первого столбца
        for (let i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            for (let a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
                }
            }
        }
        return dp[n][amt];
    }

coin_change_ii.dart

    /* Размен монет II: динамическое программирование */
    int coinChangeIIDP(List<int> coins, int amt) {
      int n = coins.length;
      // Инициализация таблицы dp
      List<List<int>> dp = List.generate(n + 1, (index) => List.filled(amt + 1, 0));
      // Инициализация первого столбца
      for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
      }
      // Переход состояний
      for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
          if (coins[i - 1] > a) {
            // Если целевая сумма превышена, монету i не выбирать
            dp[i][a] = dp[i - 1][a];
          } else {
            // Сумма двух решений: не брать или взять монету i
            dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
          }
        }
      }
      return dp[n][amt];
    }

coin_change_ii.rs

    /* Размен монет II: динамическое программирование */
    fn coin_change_ii_dp(coins: &[i32], amt: usize) -> i32 {
        let n = coins.len();
        // Инициализация таблицы dp
        let mut dp = vec![vec![0; amt + 1]; n + 1];
        // Инициализация первого столбца
        for i in 0..=n {
            dp[i][0] = 1;
        }
        // Переход состояний
        for i in 1..=n {
            for a in 1..=amt {
                if coins[i - 1] > a as i32 {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1] as usize];
                }
            }
        }
        dp[n][amt]
    }

coin_change_ii.c

    /* Размен монет II: динамическое программирование */
    int coinChangeIIDP(int coins[], int amt, int coinsSize) {
        int n = coinsSize;
        // Инициализация таблицы dp
        int **dp = malloc((n + 1) * sizeof(int *));
        for (int i = 0; i <= n; i++) {
            dp[i] = calloc(amt + 1, sizeof(int));
        }
        // Инициализация первого столбца
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
                }
            }
        }
        int res = dp[n][amt];
        // Освободить память
        for (int i = 0; i <= n; i++) {
            free(dp[i]);
        }
        free(dp);
        return res;
    }

coin_change_ii.kt

    /* Размен монет II: динамическое программирование */
    fun coinChangeIIDP(coins: IntArray, amt: Int): Int {
        val n = coins.size
        // Инициализация таблицы dp
        val dp = Array(n + 1) { IntArray(amt + 1) }
        // Инициализация первого столбца
        for (i in 0..n) {
            dp[i][0] = 1
        }
        // Переход состояний
        for (i in 1..n) {
            for (a in 1..amt) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[i][a] = dp[i - 1][a]
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
                }
            }
        }
        return dp[n][amt]
    }

coin_change_ii.rb

    ### Размен монет II: динамическое программирование ###
    def coin_change_ii_dp(coins, amt)
      n = coins.length
      # Инициализация таблицы dp
      dp = Array.new(n + 1) { Array.new(amt + 1, 0) }
      # Инициализация первого столбца
      (0...(n + 1)).each { |i| dp[i][0] = 1 }
      # Переход состояний
      for i in 1...(n + 1)
        for a in 1...(amt + 1)
          if coins[i - 1] > a
            # Если целевая сумма превышена, монету i не выбирать
            dp[i][a] = dp[i - 1][a]
          else
            # Сумма двух решений: не брать или взять монету i
            dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
          end
        end
      end
      dp[n][amt]
    end

Визуализация кода

Во весь экран >

### 3. Оптимизация пространства

При оптимизации памяти способ остается тем же самым: достаточно убрать измерение, отвечающее за виды монет:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
coin_change_ii.py

    def coin_change_ii_dp_comp(coins: list[int], amt: int) -> int:
        """Размен монет II: динамическое программирование с оптимизацией памяти"""
        n = len(coins)
        # Инициализация таблицы dp
        dp = [0] * (amt + 1)
        dp[0] = 1
        # Переход состояний
        for i in range(1, n + 1):
            # Прямой обход
            for a in range(1, amt + 1):
                if coins[i - 1] > a:
                    # Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a]
                else:
                    # Сумма двух решений: не брать или взять монету i
                    dp[a] = dp[a] + dp[a - coins[i - 1]]
        return dp[amt]

coin_change_ii.cpp

    /* Размен монет II: динамическое программирование с оптимизацией памяти */
    int coinChangeIIDPComp(vector<int> &coins, int amt) {
        int n = coins.size();
        // Инициализация таблицы dp
        vector<int> dp(amt + 1, 0);
        dp[0] = 1;
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[a] = dp[a] + dp[a - coins[i - 1]];
                }
            }
        }
        return dp[amt];
    }

coin_change_ii.java

    /* Размен монет II: динамическое программирование с оптимизацией памяти */
    int coinChangeIIDPComp(int[] coins, int amt) {
        int n = coins.length;
        // Инициализация таблицы dp
        int[] dp = new int[amt + 1];
        dp[0] = 1;
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[a] = dp[a] + dp[a - coins[i - 1]];
                }
            }
        }
        return dp[amt];
    }

coin_change_ii.cs

    /* Размен монет II: динамическое программирование с оптимизацией памяти */
    int CoinChangeIIDPComp(int[] coins, int amt) {
        int n = coins.Length;
        // Инициализация таблицы dp
        int[] dp = new int[amt + 1];
        dp[0] = 1;
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[a] = dp[a] + dp[a - coins[i - 1]];
                }
            }
        }
        return dp[amt];
    }

coin_change_ii.go

    /* Размен монет II: динамическое программирование с оптимизацией памяти */
    func coinChangeIIDPComp(coins []int, amt int) int {
        n := len(coins)
        // Инициализация таблицы dp
        dp := make([]int, amt+1)
        dp[0] = 1
        // Переход состояний
        for i := 1; i <= n; i++ {
            // Прямой обход
            for a := 1; a <= amt; a++ {
                if coins[i-1] > a {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a]
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[a] = dp[a] + dp[a-coins[i-1]]
                }
            }
        }
        return dp[amt]
    }

coin_change_ii.swift

    /* Размен монет II: динамическое программирование с оптимизацией памяти */
    func coinChangeIIDPComp(coins: [Int], amt: Int) -> Int {
        let n = coins.count
        // Инициализация таблицы dp
        var dp = Array(repeating: 0, count: amt + 1)
        dp[0] = 1
        // Переход состояний
        for i in 1 ... n {
            for a in 1 ... amt {
                if coins[i - 1] > a {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a]
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[a] = dp[a] + dp[a - coins[i - 1]]
                }
            }
        }
        return dp[amt]
    }

coin_change_ii.js

    /* Размен монет II: динамическое программирование с оптимизацией памяти */
    function coinChangeIIDPComp(coins, amt) {
        const n = coins.length;
        // Инициализация таблицы dp
        const dp = Array.from({ length: amt + 1 }, () => 0);
        dp[0] = 1;
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            for (let a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[a] = dp[a] + dp[a - coins[i - 1]];
                }
            }
        }
        return dp[amt];
    }

coin_change_ii.ts

    /* Размен монет II: динамическое программирование с оптимизацией памяти */
    function coinChangeIIDPComp(coins: Array<number>, amt: number): number {
        const n = coins.length;
        // Инициализация таблицы dp
        const dp = Array.from({ length: amt + 1 }, () => 0);
        dp[0] = 1;
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            for (let a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[a] = dp[a] + dp[a - coins[i - 1]];
                }
            }
        }
        return dp[amt];
    }

coin_change_ii.dart

    /* Размен монет II: динамическое программирование с оптимизацией памяти */
    int coinChangeIIDPComp(List<int> coins, int amt) {
      int n = coins.length;
      // Инициализация таблицы dp
      List<int> dp = List.filled(amt + 1, 0);
      dp[0] = 1;
      // Переход состояний
      for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
          if (coins[i - 1] > a) {
            // Если целевая сумма превышена, монету i не выбирать
            dp[a] = dp[a];
          } else {
            // Сумма двух решений: не брать или взять монету i
            dp[a] = dp[a] + dp[a - coins[i - 1]];
          }
        }
      }
      return dp[amt];
    }

coin_change_ii.rs

    /* Размен монет II: динамическое программирование с оптимизацией памяти */
    fn coin_change_ii_dp_comp(coins: &[i32], amt: usize) -> i32 {
        let n = coins.len();
        // Инициализация таблицы dp
        let mut dp = vec![0; amt + 1];
        dp[0] = 1;
        // Переход состояний
        for i in 1..=n {
            for a in 1..=amt {
                if coins[i - 1] > a as i32 {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[a] = dp[a] + dp[a - coins[i - 1] as usize];
                }
            }
        }
        dp[amt]
    }

coin_change_ii.c

    /* Размен монет II: динамическое программирование с оптимизацией памяти */
    int coinChangeIIDPComp(int coins[], int amt, int coinsSize) {
        int n = coinsSize;
        // Инициализация таблицы dp
        int *dp = calloc(amt + 1, sizeof(int));
        dp[0] = 1;
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= amt; a++) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a];
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[a] = dp[a] + dp[a - coins[i - 1]];
                }
            }
        }
        int res = dp[amt];
        // Освободить память
        free(dp);
        return res;
    }

coin_change_ii.kt

    /* Размен монет II: динамическое программирование с оптимизацией памяти */
    fun coinChangeIIDPComp(coins: IntArray, amt: Int): Int {
        val n = coins.size
        // Инициализация таблицы dp
        val dp = IntArray(amt + 1)
        dp[0] = 1
        // Переход состояний
        for (i in 1..n) {
            for (a in 1..amt) {
                if (coins[i - 1] > a) {
                    // Если целевая сумма превышена, монету i не выбирать
                    dp[a] = dp[a]
                } else {
                    // Сумма двух решений: не брать или взять монету i
                    dp[a] = dp[a] + dp[a - coins[i - 1]]
                }
            }
        }
        return dp[amt]
    }

coin_change_ii.rb

    ### Размен монет II: динамическое программирование с оптимизацией памяти ###
    def coin_change_ii_dp_comp(coins, amt)
      n = coins.length
      # Инициализация таблицы dp
      dp = Array.new(amt + 1, 0)
      dp[0] = 1
      # Переход состояний
      for i in 1...(n + 1)
        # Прямой обход
        for a in 1...(amt + 1)
          if coins[i - 1] > a
            # Если целевая сумма превышена, монету i не выбирать
            dp[a] = dp[a]
          else
            # Сумма двух решений: не брать или взять монету i
            dp[a] = dp[a] + dp[a - coins[i - 1]]
          end
        end
      end
      dp[amt]
    end

Визуализация кода

Во весь экран >

##### Оставляйте свои идеи, вопросы и предложения в комментариях