阿里一面凉了之旅
昨天才投的阿里巴巴，要我做的测评和在线编程题还没做，今天居然就打电话来面试了！真是猝不及防。在听我bb了半天项目经验，又问了点其他的 iOS 知识之后，面试官说：“我们来考察一下编程的思想吧！”。我说：“来吧！”，然后，然后我就跪了。。。
事情是这样的
面试官：“这道题很常见，你之前也可能听说过。”
我：“嗯，您说。”
面试官：“给你 1、2、5 三种面值的硬币，凑成 10，一共有多少种组合？”
我：“嗯。。。。我之前没听说过。。。。。让我想一下。。。。”
于是我在脑海中抽象了一下题目描述：
现有面值分别为 $v_i$ 的 N 种硬币，需要凑成 V 元，每种硬币使用次数不限，求一共有多少种凑法？
我：“嗯。。。。最直观的想法就是暴力求解。。。”
面试官：“怎么暴力求解呢？”
我：“嗯。。。。估计要用到递归。。。”（内心OS：这样复杂度好高啊）
面试官：“怎么递归呢？”
我：“嗯。。。。每种硬币加加加，然后超过范围就退回到上一种状态。。。然后尝试下一种”（内心OS：复杂度好高！估计要用动态规划来优化下，咋搞呢）
面试官：“能说一下代码会有哪些结构吗？”
我：“*……&*@!@#)(&&)”（我也不知道我瞎说了些啥，反正答得很烂）
再又聊了一点点别的东西之后，
面试官：“好的，我会如实反映这次面试的情况。应该会在一周之内联系你，如果两周都没有联系你，那就不用再等了。”
我（带着哭腔）：“好的我清楚了T^T”
挂掉电话之后
卧槽！这不就是一个动态规划吗！我咋这都没想出来！让我写一下代码！
思路：
我们需要数组 T[i][j] 表示用前 i 种硬币凑出 j 元时所有的组合数。
逐步增加 j 至 V，计算 T[i][j] 的规则如下：
遍历第 i 种硬币使用的个数，从 0（不使用）到不超过 V 的个数，记录为 k。当前硬币面值记为 v。
T[i][j] += T[i-1][j-k*v]
也就是我们考虑第 i 种硬币使用 1 个、2 个、3 个的情况，每种情况的组合数分别对应不使用这种硬币时，减去这种硬币当前凑出的面值的组合数，做一个累加就可以了。
Java实现：
1 | public class Main { |
需要注意的是，我们需要给二维数组 T 一个合适的初始值。当 j == 0 时，也就是需要凑成 0 元钱的时候，无论硬币有多少种，我们都有 1 种凑法：那就是不用凑。
从这个故事我们学到了
这道题确实很简单，而且又是我刚刚才学过的动态规划法。事实上我挂掉电话后用了不到半个小时就写出来了。也许是刚学过动态规划还不太熟练、也许是面试时太紧张、也许是面试过程中大脑傻掉了，反正答的很不好，还是自己太菜啊！面试官特意说两个星期内没收到后续结果就是凉了，估计是在暗示我真的凉了吧。。。我自己是感觉凉了。。
痛定思痛吧！继续努力！为找到实习而奋斗！
如果万一没凉……
虽然概率趋近于 0，但如果万一我没凉，还收到了后续面试的通知的话……我就用阿里的支付宝给贫困山区的小朋友捐 10 块钱辣条钱！
4.7 Update:
震惊！居然没凉！已捐款10元。