памятка в переполнении стека
Учитывая результаты команды по крикету, найдите / распечатайте все конфиги / способы получить результат. Есть 3 способа забить 2, 3 и 7
Пример:
Оценка: 10
Выход:
(0,1,1)
(0,2,2)
(0,0,5)
void out(int score, int two, int three, int seven)
{
if(score == 0)
{
cout << "(" << two << ", " << three << ", " << seven << ")" << endl;
}
else if (score < 0)
{
return;
}
else
{
outputs(score - 7, two, three, seven + 1);
outputs(score - 3, two, three + 1, seven);
outputs(score - 2, two + 1, three, seven);
}
return;
}
Я получаю правильные ответы, но с повторениями, а также хотел использовать памятку, которую я действительно запутал, как реализовать
(0, 1, 1)
(0, 1, 1)
(2, 2, 0)
(2, 2, 0)
(2, 2, 0)
(2, 2, 0)
(2, 2, 0)
(2, 2, 0)
(5, 0, 0)
Решение
Чтобы избежать повторения, вы должны наложить порядок, например, не позволяя использовать счет 7 если вы ранее использовали счет 3,
void out(int score, int two, int three, int seven, int maxscore)
{
...
else {
if (maxscore >= 7) output(score-7, two, three, seven+1, 7);
if (maxscore >= 3) output(score-3, two, three+1, seven, 3);
if (maxscore >= 2) output(score-2, two+1, three, seven, 2);
}
}
Использование мемоизации вместо этого было бы более сложным (и даже, вероятно, не очень полезным) в этой проблеме, потому что вы ищете перечисление всех решений (а не только их подсчет).
Идея запоминания состоит в том, чтобы сохранить таблицу, чтобы избежать повторного вычисления одной и той же подзадачи. В этом случае подзадача определяется баллом и максимальным баллом, который вы можете использовать, однако решение должно учитывать также, сколько двух, трех и семи вы уже использовали, и если вы также добавите их в ключ, то каждый ключ будет посещен только один раз (поэтому нет смысла пытаться его запомнить).
Вещи разные, если вам нужно только подсчитывать во сколько разных способов вы можете получить оценку, потому что в этом случае решение подзадачи — это просто число, и вы можете использовать его для решения исходной задачи.
Другие решения