击鼓传花游戏-动态规划之题解之题解

先小声BB

大家先听我BB一些心得（废话）咱们再进行击鼓传花游戏~

作为一个半年前对算法望而却步的前端工程师，最近开始系统地学习一些算法知识（推荐修言大佬的算法小册）。虽然还是不能熟练的掌握，但是能清楚的感受到自己对算法的那股恐惧感消失了。（算法之前就像一只高等级的boss，没系统学基础之前连鉴定都会失败，系统学基础之后这个boss仍然很难杀，但是可以鉴定出他的属性了），期间也学习了一些关于学习的理论，总结起来有以下三点（自己瞎编的）：

1.看得懂和写得出来中间还差十万八千里

2.复杂的问题简单化，简答的问题熟练化。

3.费曼学习法（真正的学会一个技能就是你能用浅显易懂的语言教会别人这个技能）

第一点其实是描述了一种一看就懂，一做就不会的情景，自己之前会翻技术社区的一些排序算法看，类似的文章看了不下四五篇，看的时候觉得自己很清楚，但是在做题的时候，会有一种不知道怎么下笔的感觉。

其原因其实就是看得懂和会做学习一个知识的两个level，而且两者之间需要大量的刻意练习。

第二点其实对学习算法很有帮助，虽然我们暂时锤不赢这个大boss，但是我们可以把算法拆成小boss打，小boss打不过就再拆成精英怪来打。
从数据结构来拆分，可以拆分出：

• 字符串
• 数组
• 链表
• 二叉树
• 队列
• 图
• …

从解题思路来拆分，可以拆分出：

• 深度优先搜索

• 广度优先搜索

• 贪心算法

• 动态规划

• ….

我们其实要做的就是踏实的练习这些细分的知识块，从而来学习和摸索算法这个整体的模块。

第三点就是为什么要写这篇文章，我希望可以用文章的形式记录自己学习算法的一些关键性节点，顿悟性的节点。然后尝试用自己的理解把一些复杂的概念用我自己能懂的语言说出来，然后发出来给大佬们看看，能给点指导批评意见（不知道你们有没有这种感觉，就是那种你学了但是你不知道你学的东西是不是对的，很多知识的学习都有种不确定性，），给比自己还新手的新手看看可能会给到一点启发。(少走弯路)
BB到此结束，留点话在下一篇文章（if(!!下一篇文章)）讲讲,解析来让我们一起来击鼓传花游戏吧~

击鼓传花

贴两张图让不知道这个游戏机制的同学了解一下游戏机制，接下来贴题目~

头皮发麻的小伙伴先别走，我来给你们换个题，以题目中的示例1为例

n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3
复制代码

说：有5个小朋友玩丢球，这个几个小朋友并不是所有人都关系好，他们拿到球之后只会把球丢给关系好的小伙伴，比如0号小朋友拿到球只会给2号和4号（从relation数组中得到的信息），每次开球都是0号小朋友， 问丢了3次后，球要到4号小朋友手上有几种丢法?

深度优先+递归

题目的第一种解法是把整个题转换成图来求路径数量，每个relation中的元素就是一条有向边，之后使用深度优先+递归的方式解决，这里我们不深入讨论，有兴趣的可以看看题解，我们重点把眼光放在第二种解法上：

动态规划（Dynamic Programming）

按照我目前的理解，动态规划其实就是我们熟悉的找规律，我们需要找到这个规律的起始值（边界情况）和规律（动态转移方程），我们先抛开这些专业名词，先去按照基本逻辑去找一下规律。

首先，这个球一开始是在0号小朋友的手上，当开始丢球的时候，这个球会有几种情况呢？我们根据relation中所描述的小朋友之间的关系，知道0号小朋友和2号，4号两个小朋友玩得好，所以只有下面两种情况：

1. 从0丢给了2
2. 从0丢给了4

所以第一轮丢球的结束后，每个小朋友可能拿到球的途径，为：

那到了第二轮的时候呢？第一轮的时候我们已知球可能在2号或者4号小朋友的手里，根据他们的要好关系relation我们可以知道，2号的好哥们是0号1号和3号，4号呢？4号没有好哥们（惨）！

那我们第二轮结束之后可能是什么情况呢？

那么第三轮呢？我们从第一轮第二轮中已经可以尝试着去找一找这个规律了。每一轮的状态其实是上一轮的状态和relaiton之间根据某种逻辑推理出来的，这个逻辑其实就是我们说的状态转移方程，而边界条件其实就是我们游戏的初始化的时候0号小玩家拿着球。如果我们用数组来存放每一轮玩家可能的值，那么从初始化到第二轮结束，我们得到的数据如下：

[1,0,0,0,0]//第一轮开始之前，只有0号小朋友拿球
[0,0,1,0,1]//第二轮开始之前，只有2，4两个小朋友可能持球，且持球的途径都只有一种
[1,1,0,1,0]//第三轮开始之前，只有0,1,3三个小朋友可能持球，且持球的途径都只有一种

复制代码

那么第三轮我们可以拿到第二轮的信息，再通过relation去生成第三轮信息，并且推出后面的所有轮次的信息：

for (let i = 0; i < k; i++) {
        for (const [from, to] of relation) {
            dp[i + 1][to] += dp[i][from];
        }
    }
    //得出第三轮的情况为[0,0,1,0,3]
复制代码

那么我们需要返回的就是k轮次，也就是例题中的第三轮结束后的n-1(编号4)小朋友的可能拿球途径3。
看到这里有人就要问了，哎呀你这个题目为什么叫动态规划之题解之题解，因为我还在学习如何使用动态规划做题，然后看到这道题的题解的时候就有点懵逼，贴一下官网题解：

对于一个数学基础和算法基础比较差的同学来说（我说我自己），会给我一种我连抄都不会抄的错觉，这种复杂的数学符号和公式（其实懂了之后也不复杂）其实在一定程度上会加大我对这种解题思路的理解的困难程度。所以我就是想通过自己的理解，把这些数学公式用简单逻辑来整理成文，具体原因在小声BB环节也说过了，这里就不啰嗦了~

胡思乱想

当我把这个道题目拉回到现实视角，其实还是挺有意思的。比如公司年会上也会有这种击鼓传花的活动，用一个东西互相传递，音乐停止后东西在谁手上谁就要上台表演节目或者接受惩罚。通过relation条件可以发现，这个活动其实不是一个概率均等的游戏，这个游戏在一定程度上可以反映出一个人在社交圈子（比如公司内）的受欢迎程度。因为你在relation数组元素中的第二位越多，最终球在你手上的概率也就越大，希望大家都可以做relation元素的第二位~

还有就是最近买了一本叫刻意联系的书，也忘了是哪个大佬推荐的。快递已经到公司楼下了，晚些时候看完给大家写写读后感啥的。

算法的学习才刚刚开始，对于一些人来说可能一个四年的前端去学习算法有些晚了，但是对于我自己来说只要开始，就不晚~