ARTS w08-Combination Sum

这个月一篇都没写，赶在最后一天完成一篇。

Algorithm

leetcode 216. Combination Sum III，给出两个整数k、n，求所有 k个整数和等于n 的集合，集合中每个数不重复。

Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]

Example 2:
Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

代码：

class Solution(object):
    def combinationT(self, k, n, res, s=1, header=[]):

        if k==1:
            total = sum(header)
            last = n-total
            if not header:
                if last > 0 and last<= 9:
                    res.append([last])
            elif last>header[-1] and last<=9:
                res.append(header+[last])
        else:
            for i in range(s, 10):
                if sum(header)+i>n:
                    continue
                self.combinationT(k-1, n, res, i+1, header+[i])
        
        return res

    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        return self.combinationT(k, n, [])

一次通过！

Review

Reimagining Trusted Intermediaries 文章认为加密货币有可能促成下一次规模化的创新浪潮，原因在于：1. 全球化的信任下滑，对于权威机构的信任度多年来在逐渐下降，不论是媒体、学校还是银行，文章给出了近30年的信任下降的数据图表。2. 区块链 = 无需信任的技术。货币是全球最大的信任市场，而可编程货币正在侵入现有的金融栈（finacial stack）。但去中心化需要昂贵的成本，交易的吞吐量极低，问题是什么时候去中心的益处大于其成本？当好处大于成本的时候，区块链技术才能大规模使用。那么我们现在处于何处？我们可能处于互联网兴起时代的1995年，如果回到1995年你会做什么？现在我们又该做什么？目前区块链的应用场景还很模糊，需要多长的时间来证明这项技术也是未知的，但有两件事是我们现在能做的：1. 关注带原生货币的产品，2. 保持耐心;)。

Tips

这周做了一道算法题Perfect Squares，讨论区里有人使用了动态规划的解法，赞叹。

class Solution:
    _dp = [0]
    
    def numSquares_dy(self, n):
        dp = self._dp
        while len(dp) <= n:
            dp += min(dp[-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1,
    
        return dp[n]

解题的时候，知道这道题可以从最优子结构去推导出最优解，但就是不知道做，原来这个就是动态规划了。能用动态规划解决的问题的特点：1. 问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结 构性质。2. 无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。

Share

时间过的太快。