前语

动态规划是大家都了解与生疏的常识，十分灵敏多变，我自己也不敢说自己把握了，今天给大家介绍一道题，不只局限于动态规划做题，还会涉及到信息论，并讨论自己认知国际的视点 由于比较难，本文不会具体介绍动态规划方法，所以需求读者有一定根底，不然或许了解有困难

题目链接：可怜的小猪

有buckets 桶液体，其中 正好有一桶 含有毒药，其他装的都是水。它们从外观看起来都相同。为了弄清楚哪只水桶含有毒药，你能够喂一些猪喝，经过观察猪是否会死进行判别。不幸的是，你只需 minutesToTest 分钟时刻来确认哪桶液体是有毒的。

喂猪的规矩如下：

  1. 选择若干活猪进行喂养
  2. 能够允许小猪一起饮用任意数量的桶中的水，而且该进程不需求时刻。
  3. 小猪喝完水后，必须有 minutesToDie 分钟的冷却时刻。在这段时刻里，你只能观察，而不允许持续喂猪。
  4. 过了 minutesToDie 分钟后，一切喝到毒药的猪都会死去，其他一切猪都会活下来。
  5. 重复这一进程，直到时刻用完。

给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回 在规定时刻内判别哪个桶有毒所需的 最小 猪数 。

示例 1：

输入： buckets = 1000, minutesToDie = 15, minutesToTest = 60
输出： 5

示例 2：

输入： buckets = 4, minutesToDie = 15, minutesToTest = 15
输出： 2

示例 3：

输入： buckets = 4, minutesToDie = 15, minutesToTest = 30
输出： 2

解法

dp解析

一般来说，动态规划便是三进程

  1. 定义数组意义，多数状况是int值， dp[]或许dp
  2. 赋予初始值
  3. 找到状况搬运方程，开端递推

推到最终，大部分状况下，dp数组最终一个值便是答案

这个题，

题中有buckets,minutesToTest,minutesToDie三个变量，由于正面视点比较难思考，能够反过来， 全问题为n只小猪，能够有限的次序测验中测出毒药，一轮耗时minutesToDie，总轮数为minutesToTest/minutesToDie

所以，其子问题为i只小猪测验j轮的成果，不影响后续测验，而后续测验需求子问题的成果来递推 满意动态规划的重叠子问题和无后效性准则，一起又是求最值（简称n)，所以确认能够用动态规划（简称dp)

  • 首要定义数组意义 f(i, j)表明i只小猪，测验j轮后最多能够在多少butkets中找到毒药，明显，这是一个二维数组dp[i] [j]

  • 然后赋予初始值 dp[0] ， dp[i]都为1，相当于没有测验，由于知道必有一桶毒，所以bucket = 1时，能够肯定为有毒，dp[0]没有猪，也全为1

  • 状况搬运 假定现在状况要算f(i, j)，一轮测验后还剩余k只猪存活，而测验剩余j – 1次，能够确认，f(k, j – 1)便是f(i, j )的前一个状况，并将递推出f(i, j) 从i变为k的或许组合数为 C(i, k)，因而f(i, j) = C(i, k) * f(k, j – 1)，其中k的取值为0~i，所以最终的核算如下

    f(i,j)=∑k=0if(k,j−1)Cikf(i,j) = \sum_{k=0}^i f(k, j-1) \times C_{i}^{k}

小猪，信息论与生活

小猪，信息论与生活

到了这步，现已把握了解题钥匙，更多细节能够参阅题解， 本文并非想具体介绍题解，更多的是讨论思维

信息论

抛开dp的进程，只看开端和结尾，buckets,minutesToTest,minutesToDie都限制后，经过递推或许某种方法，咱们就能得到最少的猪数量n，也便是说，当相关信息量确认好后，答案就确认了

这给咱们一个很大提示，那便是，面临一个问题的时候，在耗费时刻去做之前，只是凭仗现已把握的信息，就能判别出能不做成。留意，这儿不是靠经历或许直觉，而是真真实实的科学，若是吸收这一思维，并勤加练习，相当多的难题能够得到解决

那现在咱们就来细心了解下这一理论吧

咱们知道，核算机的许多数据看不见摸不着，咱们将其统一设置为二进制，运用bit来记载数据，创造纷乱的信息国际。而咱们，不知道三维国际的造物主用的几进制，在这个国际的咱们无法用自己的信息来准确表达信息本身

熵

不过没关系，咱们能够一个模糊的“熵”暂时代替，表明紊乱度，越紊乱，熵越高

熵增定律：在一个孤立系统里，假如没有外力做功，其总紊乱度（熵）会不断增大

关于理科生很好了解，究竟学过 关于保洁也很好了解，究竟一个房间假如长时间不打扫，肯定会变脏 关于老师也很好了解，究竟他假如长时刻不来教室，教室肯定凌乱 关于宅男更好了解，长时间不外出不好人交流，一定……

信息熵与信息

在信息论中，信息熵表明信息的不确认程度

比方，咱们都知道，相同的内容，中文写的往往比英文薄一些，实际上，便是由于中文的信息不确认程度高，也便是信息熵大，所以所需的信息量就会少，字数也会少，往往把握1000个汉字就能敷衍日常说话，许多汉字在不同的组词下有很多不同的意义。而英文，把握5000单词都未必能说清楚

小猪，信息论与生活

可是信息熵大未必是功德，信息熵越大，不确认程度越高，其实代表信息量越少，而减少信息熵的方法，便是增加含信息量的信息，不含信息量的信息，能够归类为废话（说到这，我都不认识信息两字了）

所以方向来了！关于一件富含信息熵的工作，我只需把握满足信息量的信息，与信息熵等价，那么就能够做！

比方，明日是否下雨？，这件事信息熵很大，天气预报的成果，天上的乌云，蚂蚁搬家等等都是多多少少下降信息熵的信息

到了这儿，你能够还是会有疑惑，说来说去，最终不还是靠感觉吗？不过是用了一些科学名词归类而已

香农厉害就厉害在这儿，讲一个千万年来人说不清的感觉提取出公式，让人类的认知进入了一个全新领域。在信息论提出之后，个人认为能与这一瞬间媲美的只需阿姆斯特朗的那一小步。 公式如下

H(X)=−∑i=1np(xi)log⁡bp(xi)H(X) = -\sum_{i=1}^n p(x_i)\log_b p(x_i)

看起来挺复杂，可是了解很简单，

其中，H(X)表明随机变量X的信息熵，P(xi)表明X取值为xi的概率，logb表明以b为底的对数。

这儿的b表明信息单位的根底，假如你想二进制表明，那么b == 2 x表明工作，xi能够了解为x里边的某种元素，公式便是将X工作中，1~n种元素发生的概率求和而来，n能够了解为或许的一切状况

比方扔一枚硬币，只需两种状况，那么其信息熵为

H(X)=−∑i=12p(xi)log⁡2p(xi)=−[0.5log⁡2(0.5)+0.5log⁡2(0.5)]=1bitH(X) = -\sum_{i=1}^2 p(x_i)\log_2 p(x_i) = -\left[0.5\log_2(0.5) + 0.5\log_2(0.5)\right] = 1 bit

也便是说，只需有一个含1bit信息量的信息，就能够消灭信息熵，比方我告诉你，硬币为正面，此刻，信息熵消失

解题

回到小猪的话题，题目中H(X)信息熵，在minutesToTest,minutesToDie限制下，x为bucket数，x为1000时

H(x)=−(1/1000)∗log2(1/1000)−(1/1000)∗log2(1/1000)−…−(1/1000)∗log2(1/1000)H(x) = – (1/1000) * log2(1/1000) – (1/1000) * log2(1/1000) – … – (1/1000) * log2(1/1000)
=−1000∗(1/1000)∗log2(1/1000)=log2(1000)≈9.97= – 1000 * (1/1000) * log2(1/1000) = log2(1000) ≈ 9.97

解释：1/1000表明任何桶水都有1/1000或许是毒水，然后有1000种或许性，需求累加

咱们能够对这个成果有些感性认识，看起来信息熵的增加不是线性的，而是log，扔硬币这种五五开的工作为1，而1000桶水找1个有毒居然只需9.97，当有10000桶水时，信息熵为log2(10000) = 13.29

现在咱们考虑：多少小猪能够供给大于9.97的信息熵？从示例一中

输入：buckets = 1000, minutesToDie = 15, minutesToTest = 60
输出：5

看出，能够测验 60 / 15 = 4轮，那么合计有5种状况，那便是4种逝世的场景 + 1种存活场景，在这一状况下，“1只小猪的5种状况”能够供给的信息熵为

H=−(1/5)∗log2(1/5)−(1/5)∗log2(1/5)−…−(1/5)∗log2(1/5)H = – (1/5) * log2(1/5) – (1/5) * log2(1/5) – … – (1/5) * log2(1/5)
=−5∗(1/5)∗log2(1/5)=log2(5)≈2.3219= – 5 * (1/5) * log2(1/5) = log2(5) ≈ 2.3219

解释：1/5表明小猪等或许进入到5种状况中的一种，有5次统计，需求累加

一只小猪是这么多，那么2只猪呢？会发生 5^2 = 25种或许性，3只就会有125种或许性，核算可得

Hn=2.3219nHn = 2.3219 n

所以

n=H(x)/H(n)=9.97/2.3219≈4.292n = H(x) / H(n) =9.97 /2.3219 ≈ 4.292

关于示例一，需求至少4.3头猪才干供给答案

当buckets变化时，原题的解题代码为

class Solution {
  public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    int times = minutesToTest / minutesToDie + 1;
    double time = Math.log(buckets) / Math.log(times); // 信息熵相除
    return (int)Math.ceil(time);
   }
}

后记

信息论现在广泛运用在了压缩编码，通信协议和设计等的底层算法理论，相等于给后人研究算法供给了一个天花板，只需你的算法成果没到达信息论理论极限，就有提升空间，要是超过了，那你肯定是错的

当咱们重新审视这一解法，除了感到少许震撼之外，难免会有疑问，比方，

  • 你或许猎奇小猪怎么喝水才干在5只的状况下测1000桶水

能够参阅另一篇文章： 小兔喝水

  • 为什么小猪算出来的信息熵能够和水的信息熵等价相除？

明显，信息熵便是信息熵，他本身是能够比较的，并不存在什么xx的信息熵。许多东西也不存在什么中西之分，只需真假之分

所以，咱们应该愈加关注的，是跳脱出工作的表面特点，去提取出实质的信息量，日子中无法严格按照公式去核算，可是，当咱们做一些比较重要的决策时，能够再想想，我是否现已把握了满足的信息？

什么叫满足的信息？

比方选取高考志愿，在我看来至少需求的信息有：目标专业常识与未来远景，目标大学的地理位置与名气，自己的喜爱等等，愈加深层次的由于我并不精通信息论专业，可是期望你读完有所收获~

参阅链接：

www.zhihu.com/question/60… zh.wikipedia.org/wiki/%E7%86… leetcode.cn/problems/po…