蓝桥杯第八天

超、凢脫俗 2023-01-08 10:30 146阅读 0赞

# 一力扣63 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70]

*  对于一个数学题，基本上就是Cm+n-1，n-1，但是没用学习的东西
 *  不过看了题解，这道题实际上靠的时动态规划（递归不知道算不算解法之一，大部分我的递归超时）
 *  我们要么右要么下，只有两种，所以对于dpij来说，他的思想就是dp【i】【j】=dp【i-1】【j】+dp【i】【j-1】，这是因为任意一个点的路线都来自与上方和左方
 *  因此，我们只需要设立初始值就可以进行动态规划了
 *  矩阵的初始就是边界都设定为1，意思是这里都只有1条路线

class Solution:
        def uniquePaths(self, m: int, n: int) -> int:
            ##return comb(m+n-1,n-1)
            dp=[[0]*n for _ in range(m)]
            for i in range(m):
                dp[i][0]=1
            for i in range(n):
                dp[0][i]=1
            for i in range(1,m):
                for j in range(1,n):
                    dp[i][j]=dp[i-1][j]+dp[i][j-1]
            return dp[-1][-1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 1]

# 二力扣题目70 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 2]

*  此题与上一道类似，都是动态规划
 *  我们只需要将中心的规划过程根据题目改变一下，根据阶数可以理解为1阶的规划，其中心过程是：
 *  只能1阶或者两阶，因此对第n阶台阶来说，他的方法就是res【n】=res【n-1】+res【n-2】
 *  我们设立的初始值就是前两节，1与2，这样我们的模型就完成了

class Solution:
        def climbStairs(self, n: int) -> int:
            res=[0 for _ in range(n)]
            if n<=2:
                return n
            res[0],res[1]=1,2
            for i in range(2,n):
                res[i]=res[i-1]+res[i-2]
            return res[-1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 3]

# 三力扣78 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 4]

*  这道题大概有两种解法比较适合，一种是广度优先算法，和深度优先算法（同回溯算法）
 *  我这道题和题解后许多大佬的深搜同理，但是我发现这样理解很强：
 *  每个集合深搜加上一个新的对象时，就是本身集合和本身集合加上一个新元素的集合好比【1】加上2时，应当本身是【1】，【1，2】，根据这个算法，我们可以简化大多设定为函数的代码

class Solution:
        def subsets(self, nums: List[int]) -> List[List[int]]:
            
            s=[[]]
            for i in nums:
                l=len(s)
                for j in range(l):
                    c=s[j].copy()
                    c.append(i)
                    s.append(c)
            return s

秒啊~，看不懂函数迭代的可以学学我的，两层遍历，好理解哦

总结！今天学的好顺利  
ps~我理解的很好了，能不能获得优秀。如果觉得有哪里能改进的可以留个评论

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70]: /images/20221119/78e45be7ff204e2e8ba6db6fba6bd255.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 1]: /images/20221119/26d387aa3f9449e0b9981547be47fad0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 2]: /images/20221119/cb6578dc37a94ec98da1d91bc20af9e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 3]: /images/20221119/6465d736340b4f118af2009436114f76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 4]: /images/20221119/21722f14cf7046ea8886975f96c9d5d4.png