ARTS

ARTS 是陈浩（网名左耳朵耗子）在极客工夫专栏里发动的一个流动，目标是通过分享的形式来保持学习。

每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。

本周内容

Algorithm

这周的算法题是 DP 入门题: LeetCode 322 零钱兑换.

应该是动静布局最常见的题目之一了, 具体的解题思路能够先从递归的形式来. 即, 假设凑出总额为 i 所需的起码金币数量为 dp[i]. 那么 dp[i] = min(dp[i-coinA], dp[i-coinB], ...) + 1. 再转化到 DP 的思路, 下面的等式就是递推公式, base case 能够定义为 dp[0] = 0. 上面是代码:

func coinChange(coins []int, amount int) int {// dp[i] 代表总额是 i 时起码须要的硬币数量
    // dp[i] = min(dp[i-coinA], dp[i-coinB], ...) + 1
    dp := make([]int, amount+1)
    dp[0] = 0
    // 初始化为 amount+1 等价于设置初始值到无穷大, 因为总额 amount 时最多只须要 amount 个硬币
    for i := 1; i < amount+1; i++ {dp[i] = amount+1
    }

    for i := 1; i <= amount; i++ {
        for _, c := range coins {
            if i < c {continue}
            dp[i] = min(dp[i], dp[i-c]+1)
        }
    }
    if dp[amount] == amount+1 {return -1}
    return dp[amount]
}

func min(a, b int) int {
    if a < b {return a}
    return b
}

Review 文章举荐

本周的文章是一份分布式系统学习的经典材料, 或者说是一个分布式系统入门学习纲要: Distributed systems theory for the distributed systems engineer.

对于分布式系统的设计思路文中给出了超级多 实践 + 实际 的学习材料. 包含一些为老手筹备的的电子书, 一些外围概念比方 CAP 实践的解释, 最初还给出了一些值得参考的软件我的项目. 文章不长, 然而给出的材料十分空虚, 看完至多须要两三个月. 大概率前面几周的 Review 都会来自这篇文章给出的材料.

Tip 编程技巧

本周的编程毫无技巧可言.

Share 灵光一闪

真是一点都不灵光的一周.