写在前面

其实,在刚接触编程时候，对于贪心算法和动态规划的区别一直感觉比较模糊，今天就数硬币这道题，来和大家认识一下贪心算法和动态规划。

题目如下:

• 我们一共需要找money块钱
• 我们有一些硬币,币值在数组中，比如[1,3,4]
  • 表示我们一共有3个硬币，币值分别为1，3，4
• 问题：如何找钱，能使用最少的硬币数？

贪心算法的分析

拿到这个问题，我们首先就会去想，大币值能顶几个小币值，那么我们尽量去取大的币值，不就能够取到最少的硬币数了吗？

• 这种尽量去拿大的，拿不下了再拿次大的
• 这种算法就是贪心算法
• 我们可以尝试来写一下这个算法
  • 我们会发现，这个算法并不能算出最佳值
  • 以找6块，[1,3,4]硬币为例

let money = 6;
let corn = [1, 3, 4];
function greedy(money, corn) {
  let cnt = 0;
  for (let i = corn.length - 1; i >= 0; i--) {
    while (money >= corn[i]) {
      money -= corn[i];
      cnt++;
    }
  }
  return cnt;
}

let ans = greedy(money, corn);
console.log("贪心算法", ans);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 我们可以口算，也可以看程序的输入
• ans=3
  • 显然这不是最佳答案
  • 我们先拿了4，然后3拿不下，然后连着拿两个1，一共是3个硬币
  • 但是，我们知道正确答案其实是2个硬币，2个3
• 所以来说，贪心算法并不能完成所有的需求
  • 也有一些人生的哲理吧
  • 也许偶尔的弯路能让你走得更远
  • 也类似机器学习,学到某个高峰后就会停滞，所以到不了最高峰

动态规划的分析

• 我们知道从整体每步都取比较有利的一步，最后可能拿不到最佳的效果
• 但是动态规划是从每一小点取最佳的一步，这就是贪心和动态规划最大的区别
• 动态规划最重要的就是找到状态转移方程
  • 那我们先申请一个数组let dp = new Array(money + 1).fill(Infinity);
  • 这个数组用来存放某个额值所需要的硬币数
    • 我们初始化是正无穷，是方便后面通过动态转移方案来更新dp数组
  • 下面我们来分析一下状态转移方程
    • dp[i]可以看成我在某个额值上取一个硬币，也就是dp[i-coin[j]]+1
    • 这个地方是取最小值哦！min，因为我们要找到最少的硬币数
    • 然后我们同时去遍历所有的硬币,就可以拿到dp[i]的最佳值
      • 因为i-coin[j]<i,所以dp[i-coin[j]]也是最佳值
      • 所以在最佳值上+1,dp[i]就也是最佳值了
    • 总上,我们的状态转移方程就是dp[i] = min(dp[i], dp[i - coin[j]] + 1);
      • 当然，我们要判断i - coin[j] >= 0,来保证dp[i]是存在的

let money = 6;
let coin = [1, 3, 4];
function min(a, b) {
  return a < b ? a : b;
}
function dynamic(money, coin) {
  let cnt = 0;
  let dp = new Array(money + 1).fill(Infinity);
  for (let i = 0; i < coin.length; i++) {
    dp[coin[i]] = 1;
  }
  for (let i = coin[0]; i <= money; i++) {
    for (let j = 0; j < coin.length; j++) {
      if (i - coin[j] >= 0) dp[i] = min(dp[i], dp[i - coin[j]] + 1);
    }
  }
  return dp[money];
}

let ans = dynamic(money, coin);
console.log("动态规划", ans);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 我们来模拟运行一下，为什么动态规划的结果是2
  • 在i=6的时候
    • dp[i]=Infinity
    • 循环j,分别是
      • j=0,dp[6-1]+1=>dp[5]+1=>…=>2+1=3
      • j=1,dp[6-3]+1=>dp[3]+1=>…=>1+1=2
      • j=2,dp[6-4]+1=>dp[2]+1=>…=>2+1=3
• 这样模拟了一下应该会更加清晰了

最后再贴一下对应的TypeScript代码吧！

贪心算法

let money:number = 6;
let coin:number[] = [1, 3, 4];
function greedy(money:number, coin:number[]) {
  let cnt:number = 0;
  for (let i = coin.length - 1; i >= 0; i--) {
    while (money >= coin[i]) {
      money -= coin[i];
      cnt++;
    }
  }
  return cnt;
}
let ans = greedy(money, coin);

console.log('贪心算法',ans);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

动态规划

let money:number = 6;
let coin:number[] = [1, 3, 4];
function min(a:number, b:number) {
  return a < b ? a : b;
}
function dynamic(money:number, coin:number[]) {
    let cnt = 0;
    let dp = new Array(money + 1).fill(Infinity);
    for (let i = 0; i < coin.length; i++) {
    dp[coin[i]] = 1;
    }
    for (let i = coin[0]; i <= money; i++) {
    for (let j = 0; j < coin.length; j++) {
        if (i - coin[j] >= 0) dp[i] = min(dp[i], dp[i - coin[j]] + 1);
    }
    }
    return dp[money];
}

let ans = dynamic(money, coin);
console.log("动态规划", ans);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22