找零问题与动态规划

今天岩岩抛出了一道 code war 上的题目,大意如下:

一个函数接收两个参数,第一个参数是数字,第二个参数是数字数组,求数组里的数字加起来等于第一个参数的所有情况,可以无限次使用数组里的数字。 譬如 5, [1, 2, 5],总共有

  • 1 + 1 + 1 + 1 + 1 = 5
  • 1 + 1 + 1 + 2 = 5
  • 1 + 2 + 2 = 5
  • 5 = 5 这样 4 种情况,所以返回 4。 第一个参数为 0 的时候,返回 1。

后来我发现在 leet code 也有类似的题,是个找零问题,就是不同面值的硬币组合成一个数有多少种情况。还挺有意思的,我就做了一下,用了递归:

const change = function (sum, arr) {
    const nums = arr.sort((a, b) => a - b);
    return add(sum, arr);
};

const add = function (sum, nums) {
    const min = nums[0];
    if (sum === 0 || sum === min) return 1;

    let res = 0;
    if (nums.includes(sum)) res += 1;

    for (let i = 0; i < nums.length; i++) {
        const last = sum - nums[i];
        if (last >= nums[i]) res += add(last, nums.slice(i));
    }
    return res;
}

在 code war 上是成功提交了,但在 leet code 上却超时了,性能太差了。然后岩岩在 code war 的答案里看到了这样一段代码:

const countChange = (m, c) => {
  const a = [1].concat(Array(m).fill(0));
  for (let i = 0, l = c.length; i < l; i++) 
    for (let x = c[i], j = x; j <= m; j++) 
      a[j] += a[j - x];
  return a[m];
}

看得我俩十分懵逼,苦思半天还是懵逼。于是我上网搜到了相同解法的 C++ 版本:

using namespace std;

class Solution 
{
public:
    int change(int amount, vector<int>& coins) 
    {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int coin : coins) 
        {
            for (int i = coin; i <= amount; ++i) 
            {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};

文章 说是用的动态规划(知道了这点很关键),虽然没具体解释,但这个版本的命名比上面那个 JS 版本实在是好懂太多了,dp 就是 dynamic programming 嘛,所以已经可以勉强推导他的思路:

dp 是一个长为 amount + 1 的表,依次用来记录组合成 0、1、2、3、、、amount 各有多少种情况,dp[0] 初始为 1,其他都初始为 0。

接下来循环硬币值,记录从当前硬币值到 amount 的所有组合情况。状态转移方程为:dp[i] += dp[i - coin]。什么意思呢?假设我们求 [1, 2, 5] 这三个面值组成 5 的情况,现在我先拿出一个 2,那我是不是只要再有一个 3 就可以得到 5 了,那我只要计算有多少种组合成 3 的情况就好了,即当 coin = 2 的时候,dp[5]new = dp[5]old + dp[3],以此类推。

for (int coin : coins) 
{
    for (int i = coin; i <= amount; ++i) 
    {
        dp[i] += dp[i - coin];
    }
}

以上这段代码的意思就是先计算我拿出 1 的时候,组合成 12345 的情况数,再计算当我拿出 2 的时候,组合成 2345 的情况数(加上拿出 1 时候的情况数),再计算拿出 5 的时候,组合成 5 的情况数(加上拿出 1 和拿出 2 时候的情况数),最后得出的 dp[5] 就是我们想要的结果。你可能会问我们要的是 dp[5],中间的 dp[1]dp[2]...dp[4] 有什么用,其实这就是动态规划的精髓,会把子问题的解记录(缓存)下来,因为这些子问题会在计算过程中多次用到,就不需要每次都计算了。

上述解法的大体思路其实和下面这个朴素递归是相似的,都是把问题分解为子问题进行求解,动态规划强就强在会缓存子问题的解避免重复计算从而提高效率。

const countChange = function(money, coins) {
  if (money < 0 || coins.length === 0)
    return 0
  else if (money === 0)
    return 1
  else
    return countChange(money - coins[0], coins) + countChange(money, coins.slice(1))
}

以后当你碰到一个问题,它可以分解为多个子问题,并且子问题有重叠时,就用动态规划吧。

啊,我真是太菜了……一个动态规划的题搞了半天……

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ATYUN订阅号

使用Python建立你数据科学的“肌肉记忆”

你是否曾在在搜索语法时,因为打断了数据分析流而感到沮丧?为什么你在屡次查找后仍然不记得它?这是因为你还没有足够的练习来为它建立“肌肉记忆”。

892
来自专栏用户2442861的专栏

限制QLineEdit的数值输入范围

QLineEdit *lineEdit = new QLineEdit(this);

1.5K1
来自专栏微服务生态

由学习《软件设计重构》所想到的代码review(二)

我们接第一篇来继续说明在代码review中,有哪些属于“层次结构”中的坏味道。 第一篇链接如下:http://www.jianshu.com/p/07dbf6...

902
来自专栏北京马哥教育

hiphop原理分析1

Hiphop是Facebook开发一款PHP二进制化的一个工具,最开始是由php转为C++,但是后来发现编译为c++的话,许多的时间会花费在编译代码上面,调试不...

3097
来自专栏Star先生的专栏

Tensorflow 术语表

本文主要简要介绍了广播操作、Graph(图)、Session(会话)、Tensor 等13个 Tensorflow 术语表。希望对大家了解学习 Tensorfl...

1.1K1
来自专栏生信宝典

Python学习教程(二)

输入输出 交互式输入输出 在很多时候,你会想要让你的程序与用户(可能是你自己)交互。你会从用户那里得到输入,然后打印一些结果。我们可以分别使用raw_input...

2818
来自专栏决胜机器学习

有趣的算法(三)——Hash算法

有趣的算法(三)——Hash算法 (原创内容,转载请注明来源,谢谢) 一、Hash算法 近期看到用hash实现基于hash的简单的小型数据库(传统大型数据...

3737
来自专栏猿人谷

面试必备:HashMap、Hashtable、ConcurrentHashMap的原理与区别

HashMap和Hashtable都是用hash算法来决定其元素的存储,因此HashMap和Hashtable的hash表包含如下属性:

1761
来自专栏用户2442861的专栏

数据库系统——B+树索引

http://blog.csdn.net/cjfeii/article/details/10858721

4771
来自专栏PingCAP的专栏

SuRF: 一个优化的 Fast Succinct Tries

在前一篇文章中,我简单介绍了 Succinct Data Structure,这里我们继续介绍 SuRF。

3315

扫码关注云+社区

领取腾讯云代金券