Логика включения / исключения текущего элемента в рекурсивном подходе - PullRequest
Новая
       22

Логика включения / исключения текущего элемента в рекурсивном подходе

0 голосов
/ 30 декабря 2018

В настоящее время я изучаю DP, однако ранее я сталкивался с некоторыми примерами, такими как сумма подмножеств или, как показано в этом вопросе, проблема изменения монеты, которую их решения называют рекурсивными случаями , включая текущий элемент и исключаятекущий элемент .Тем не менее, я действительно трудно понять, что / почему это реальная причина, делая такой подход.Я не могу понять нижнюю логику позади этого.Я не хочу запоминать или говорить "хм, ладно, имейте это в виду, есть подход" как этот стиль.

enter image description here

class Util
{
    // Function to find the total number of distinct ways to get
    // change of N from unlimited supply of coins in set S
    public static int count(int[] S, int n, int N)
    {
        // if total is 0, return 1 (solution found)
        if (N == 0) {
            return 1;
        }

        // return 0 (solution do not exist) if total become negative or
        // no elements are left
        if (N < 0 || n < 0) {
            return 0;
        }

        // Case 1. include current coin S[n] in solution and recurse
        // with remaining change (N - S[n]) with same number of coins
        int incl = count(S, n, N - S[n]);

        // Case 2. exclude current coin S[n] from solution and recurse
        // for remaining coins (n - 1)
        int excl = count(S, n - 1, N);

        // return total ways by including or excluding current coin
        return incl + excl;
    }

    // Coin Change Problem
    public static void main(String[] args)
    {
        // n coins of given denominations
        int[] S = { 1, 2, 3 };

        // Total Change required
        int N = 4;

        System.out.print("Total number of ways to get desired change is "
                                + count(S, S.length - 1, N));
    }
}

Я не хочу поверхностно пропускать части, так как формулы повторения действительно играют ведущую роль для динамического программирования.

1 Ответ

0 голосов
/ 30 декабря 2018

В каждой рекурсии вы хотите исследовать оба случая:

  1. используется еще одна монета типа n
  2. вы закончили с монетой типа n и переходите к следующему типу монет

Оставшаяся задача обрабатывается в обоих случаях рекурсивным вызовом.

Кстати, это решение не имеет ничего общего с динамическим программированием.

В общей проблеме powerset, учитывая (1 2 3), нас просят сгенерировать ((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ()).Мы можем использовать это с и без техники для генерации результата. 

+---+         +---------------------------+     +--------------------------------------------+
|   +-with----> ((1 2 3) (1 2) (1 3) (1)) |     |                                            |
| 1 |         |                           +-----> ((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ()) |
|   +-without-> ((2 3) (2) (3) ())        |     |                                            |
+-^-+         +---------------------------+     +--------------------------------------------+
  |
  +-------------------------------------------+
                                              |
+---+           +-------------+   +-----------+--------+
|   +-with------> ((2 3) (2)) |   |                    |
| 2 |           |             +---> ((2 3) (2) (3) ()) |
|   +-without---> ((3) ())    |   |                    |
+-^-+           +-------------+   +--------------------+
  |
  +--------------------------------+
                                   |
+---+           +-----+     +------+--------+
|   +-with------> (3) |     |               |
| 3 |           |     +----->  ((3) ())     |
|   +-without---> ()  |     |               |
+-^-+           +-----+     +---------------+
  |
  |
+-+-+
|() |
|   | <- base case
+---+
...