Найдите максимальное количество частей, которые можно разрезать на стержень

Question

Вот полная постановка задачи:

Для веревки длиной n вам нужно найти максимальное количество
частей, которое вы можете сделать так, чтобы длина каждого кусок находится в наборе {a, b, c} для
данных трех значений a, b, c

Я знаю, что оптимальное решение может быть достигнуто с помощью Dynami c Программирование, однако, я еще не изучил этот topi c, и мне нужно решить эту проблему рекурсивно. При рекурсии главное - определить подзадачу, и это то, с чем у меня в основном возникают трудности. Может ли кто-нибудь дать мне интуитивный способ подумать об этой проблеме? Что-то вроде описания рекурсии на более высоком уровне, если это имеет смысл. Есть ли более простая проблема, похожая на эту, которую я могу попробовать сначала, которая поможет мне решить эту проблему?

Заранее спасибо.

Answer 1

Это уже довольно просто, с помощью рекурсии мы можем просто проверить все возможности, за один шаг мы можем либо отрезать кусок длины a, b или c, поэтому из проблемы размера n мы получить sup-проблему меньшего размера n-x

Конечно, нам нужен базовый случай, поэтому, когда n=0 мы добились успеха, мы можем вернуть 0, в случае n < 0 мы потерпели неудачу, поэтому мы можем вернуть некоторую константу отрицательной бесконечности.

Пример псевдокода:

int solve(int n){
    if(n < 0) return -123456789; //-Infinity
    if(n == 0) return 0;
    return 1 + max(solve(n-a), solve(n-b), solve(n-c));
}

переход в динамический режим c программирование так же просто, как создание таблицы поиска мемо

int solve(int n){
    if(n < 0) return -123456789; //-Infinity
    if(n == 0) return 0;
    if(n in memo)return memo[n]
    return memo[n] = 1 + max(solve(n-a), solve(n-b), solve(n-c));
}