Dynamic Programming: Why does the code fail when I break the if statement up into 2 lines?-CodePudding

I am working on this question https://structy.net/problems/min-change in which given a vector of coins and a target amount, I need to return the minimum amount of coins that satisfy the target amount.

The variable island size represents the minimum amount of change that should be given to the customer and currentSize represents the current amount of coins it would take to reach the correct change given which coin's path they choose to check as denoted by the recursion.

I have 2 code blocks below under the bold headers and my question is what makes the not working code blocks conditionals not work?

I first check if the currnent coin paths route is valid, and if its the first valid coin path that leads to the correct change, then current miniumchange we're holding is the first valid pathway.

However if we have already had a valid pathways then it would move to the second conditional where I just get the minimum of the current pathway and the total pathway given that the current pathway returns the correct amount of change.

In the first block it is simply the 2 if the first block can be distributed as

if((currentSize != -1 && islandSize == -1) || (currentSize != -1 && (currentSize   1 < islandSize))) islandSize = currentSize   1

And since currentSize must be true in both the cases it can be broken down further into

/// first valid size
if((currentSize != -1 && islandSize == -1) islandSize = currentSize   1; 
/// the new minimum
if(currentSize != -1 && currentSize   1 < islandSize) islandSize = currentSize   1;

Since the second conditional won't modify islandSize if it is already smaller than the currentSize, the code:

/// 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);

should only update the islandSize if such a path exists smaller than the currentSize as well.

Can someone assist me on where I am going wrong here? And if I can ask the question any better I would love that critique.

Working Code

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;
}

Not working code

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;
}

CodePudding user response：

The conditional statement

if(currentSize != -1 && (islandSize == -1 || currentSize   1 < islandSize))
{
    islandSize = currentSize   1;
}

could be rewritten as

if(currentSize != -1)
{
    if (islandSize == -1 || currentSize   1 < islandSize)
    {
        islandSize = currentSize   1;
    }
}

The two statements

if(currentSize != -1 && islandSize == -1)
{
    islandSize = currentSize   1;
}
if(currentSize != -1)
{
    islandSize = min(islandSize, currentSize   1);
}

could be rewritten as

if(currentSize != -1)
{
    if (islandSize == -1)
    {
        islandSize = currentSize   1;
    }
    else
    {
        islandSize = min(islandSize, currentSize   1);
    }
}

The logic of the conditions just simply isn't the same: If currentSize != -1 is true then the first variant will only assign to islandSize if the second part of the condition is true; While in the second will always assign to islandSize.