Я работаю над этим вопросом https://structy.net/problems/min-change, в котором, учитывая вектор монет и целевую сумму, мне нужно вернуть минимальное количество монет, удовлетворяющее целевому количеству.
Переменный размер острова представляет собой минимальную сумму сдачи, которая должна быть предоставлена покупателю, а currentSize представляет текущую сумму монет, которая потребуется для получения правильной сдачи, учитывая, какой путь монеты они выбирают для проверки, как обозначено рекурсией.
У меня есть 2 блока кода ниже, выделенные жирным шрифтом, и мой вопрос заключается в том, что делает неработающие условные блоки кода неработающими?
Сначала я проверяю, действителен ли текущий маршрут путей монет, и если это первый действительный путь монет, который ведет к правильному изменению, то текущий минимальный обмен, который мы удерживаем, является первым действительным путем.
Однако, если у нас уже есть действительные пути, то он перейдет ко второму условному, где я просто получу минимум текущего пути и общий путь, учитывая, что текущий путь возвращает правильное количество изменений.
В первом блоке это просто 2, если первый блок можно распределить как
if ((currentSize != -1 && islandSize == -1) || (currentSize != -1 && (currentSize + 1 < islandSize))) islandSize = currentSize + 1
И поскольку currentSize должен быть истинным в обоих случаях, его можно разбить на
/// first valid size
if ((currentSize != -1 && islandSize == -1) islandSize = currentSize + 1;
/// the new minimum
if (currentSize != -1 && currentSize + 1 < islandSize) islandSize = currentSize + 1;
Поскольку второе условное выражение не изменит размер острова, если он уже меньше текущего размера, код:
/// first valid size
if ((currentSize != -1 && islandSize == -1) islandSize = currentSize + 1;
// updates islandSize min if it there exists a smaller current size
if (currentSize != -1) islandSize = min(islandSize, currentSize + 1);
следует обновлять только islandSize, если такой путь меньше, чем currentSize.
Может ли кто-нибудь помочь мне понять, где я ошибаюсь? И если бы я мог задать вопрос лучше, мне бы понравилась эта критика.
unordered_map<int, int> memo;
int minChange(int amount, std::vector<int> coins) {
if (memo.count(amount)) return memo[amount];
if (amount == 0) return 0;
if (amount < 0) return -1;
int islandSize = -1;
for(auto it : coins){
int currentSize = minChange(amount - it, coins);
memo[amount-it] = currentSize;
if (currentSize != -1 && (islandSize == -1 || currentSize + 1 < islandSize)) islandSize = currentSize + 1;
}
// todo
return islandSize;
}
int minChange(int amount, std::vector<int> coins) {
if (memo.count(amount)) return memo[amount];
if (amount == 0) return 0;
if (amount < 0) return -1;
int islandSize = -1;
for(auto it : coins){
int currentSize = minChange(amount - it, coins);
memo[amount-it] = currentSize;
if (currentSize != -1 && islandSize == -1 ) islandSize = currentSize + 1;
if (currentSize != -1) islandSize = min(islandSize, currentSize + 1);
}
// todo
return islandSize;
}





Условное утверждение
if (currentSize != -1 && (islandSize == -1 || currentSize + 1 < islandSize))
{
islandSize = currentSize + 1;
}
можно было бы переписать как
if (currentSize != -1)
{
if (islandSize == -1 || currentSize + 1 < islandSize)
{
islandSize = currentSize + 1;
}
}
Два утверждения
if (currentSize != -1 && islandSize == -1)
{
islandSize = currentSize + 1;
}
if (currentSize != -1)
{
islandSize = min(islandSize, currentSize + 1);
}
можно было бы переписать как
if (currentSize != -1)
{
if (islandSize == -1)
{
islandSize = currentSize + 1;
}
else
{
islandSize = min(islandSize, currentSize + 1);
}
}
Логика условий просто не одинакова: если currentSize != -1 истинно, то первый вариант будет присвоен islandSize только в том случае, если вторая часть условия истинна; В то время как во втором всегда будет назначаться islandSize.