Динамическое программирование: почему код дает сбой, когда я разбиваю оператор if на 2 строки?

Я работаю над этим вопросом 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;
}

Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
0
63
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Условное утверждение

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.

Другие вопросы по теме