Блог

Главная - Вопросы по программированию - Пытаюсь решить несколько способов создания монет, но я не могу понять, где моя логика ошибочна

Пытаюсь решить несколько способов создания монет, но я не могу понять, где моя логика ошибочна

#javascript #algorithm #dynamic-programming

#javascript #алгоритм #динамическое программирование

Вопрос:

пытаюсь решить эту проблему.

Вы работаете за кассой на ярмарке развлечений, и у вас есть различные типы монет, доступные вам в бесконечных количествах. Значение каждой монеты уже задано. Можете ли вы определить количество способов внесения изменений для определенного количества единиц, используя данные типы монет?

 Sample Input 1
10 4
2 5 3 6

Sample Output 1
5
Explanation 1

There are five ways to make change for n = 10 units using coins with values given by C= [2,5,3,6]:

1) {2,2,2,2,2}
2) {2,2,3,3}
3) {2,2,6}
4) {2,3,5}
5) {5,5}

Код, который я написал:

 const getWays = (n, c) => {
  let m = c.length

  let matrix = Array.from(new Array(m   1), () => Array(n   1).fill(0))
  console.log(matrix);


  for (let i = 0; i <= m; i  ) {
    matrix[i][0] = 1
  }
  for (let j = 1; j <= n; j  ) {
    matrix[0][j] = 0
  }

  for (let i = 1; i <= m; i  ) {
    for (let j = 1; j <= n; j  ) {
      if (c[i] > j) matrix[i][j] = matrix[i - 1][j]
      else {
        matrix[i][j] = matrix[i - 1][j]   matrix[i][j - c[i]]
      }
    }
  }
}

console.log(getWays(10, [2, 5, 3, 6])) //5

Я не могу понять, где моя логика нарушается при присвоении значений матрице. Что я делаю не так?

Комментарии:

1. Нет возвращаемого значения в getWays функции

Ответ №1:

Проверьте этот рекурсивный алгоритм.

 function getWays(n, c) {
  const len = c.length
  if (n < 0 || len < 1) return 0
  if (len == 1) {
    if (n % c[0] == 0) return 1
    return 0
  }
  let cnt = 0
  for (let i = 0; i < len - 1; i  ) {
    for (let j = c[i]; j <= n; j  = c[i]) {
      cnt  = getWays(n - j, c.slice(i   1))
    }
  }
  if (n % c[len - 1] == 0) cnt  
  return cnt
}

console.log(getWays(10, [2, 5, 3, 6])) //5