Решение задачи в Excel методом динамического программирования

Для решения этой задачи методом динамического программирования в Excel, мы можем использовать следующий подход:

1. **Инициализация таблицы**: Создайте таблицу, где каждая строка соответствует одному из возможных слагаемых (3, 4, 7), а столбцы - числам от 1 до 96 (или до меньшего числа, если вы уверены, что решение найдется раньше).

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

3. **Формулы**:
- Если текущее число меньше слагаемого, то копируем значение из ячейки выше.
- Если текущее число равно слагаемому, то записываем 1, так как число можно представить одним слагаемым.
- Если текущее число больше слагаемого, то минимум из двух значений: значение из ячейки выше или (1 + значение из ячейки в этой строке, но для числа, уменьшенного на текущее слагаемое).

4. **Реализация в Excel**:
- В первой строке (заголовки столбцов) укажите числа от 1 до 96.
- В первом столбце (заголовки строк) укажите слагаемые 3, 4, 7.
- Заполните таблицу согласно описанным правилам.

Пример формулы для ячейки, соответствующей слагаемому 3 и числу 10:
- Если в ячейке выше (для слагаемого 4 и числа 10) стоит значение \( X \), и в ячейке этой же строки, но для числа 7 (10 - 3 = 7), стоит значение \( Y \), то в текущей ячейке будет минимум из \( X \) и \( Y + 1 \).

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