首页 > 编程语言 >代码随想训练营第三十九天(Python)| 62.不同路径、63. 不同路径 II、343. 整数拆分

代码随想训练营第三十九天(Python)| 62.不同路径、63. 不同路径 II、343. 整数拆分

时间:2023-11-23 20:44:08浏览次数:32  
标签:路径 Python 第三十九 int range obstacleGrid 拆分 dp

62.不同路径

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # dp[i][j] 代表到达 dp[i][j] 有多少不同路径
        dp = [[0]*n for _ in range(m)]

        # 初始化
        for i in range(m):
            dp[i][0] = 1

        for j in range(n):
            dp[0][j] = 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[m-1][n-1]

63. 不同路径 II

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
            return 0
        dp = [[0]*n for _ in range(m)]

        for i in range(m):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = 1
            else:
                break

        for j in range(n):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = 1
            else:
                break

        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    continue
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[m-1][n-1]

343. 整数拆分

class Solution:
    def integerBreak(self, n: int) -> int:
        # dp[i] 代表拆分整数 i 获取的最大值
        dp = [0] * (n+1)

        # 初始化 dp 数组
        dp[2] = 1

        # 遍历 dp 数组
        for i in range(2, n+1):
            # 从 1 开始拆分整数
            for j in range(1, i//2 + 1):
                dp[i] = max(dp[i], j*(i-j), j*dp[i-j])

        return dp[n]

标签:路径,Python,第三十九,int,range,obstacleGrid,拆分,dp
From: https://www.cnblogs.com/yixff/p/17836754.html

相关文章

  • 运行python的几种方式
    通过cmd终端去运行按住win+r打开命令提示符,然后输入python,就可以进入python环境,输入你需要指定的python代码即可。#注意:这种方法只是建议临时使用一下,因为午饭保存数据。通过记事本新建一个记事本文档(后缀是否修改为.py不影响)里面输入python代码,一样通过cmd窗口去执行。......
  • 聪明办法学python.
    循环:foriinrange(x,y,z):     [x,y),z为步长,省略第一个参数默认为0,省略第三个参数默认为1.     while条件:     continue跳过此次循环     break跳出当前整个循环     pass占位符,不会被运行字符串:单引号'和双引号"......
  • Python TASK02 :数据类型操作
    #数据类型操作####常用内置类型BUILTINTYPES1.整数Integer(int)2.浮点数Float3.布尔值Boolean(bool)4.类型Type(是的,“类型”也是种类型!)严格的来说,Type是一种类的对象,Python是一门“面向对象友好”的语言 so:print(type(2))--><class'int'>......
  • Python Chap3 变量与函数
    #变量与函数##变量1.变量是一个**名字**,它所指代的是一段数据2.使用=来对这段数据的区域进行赋值x=53.新的值会覆盖掉旧的值4.新值的数据类型不必与旧值相同##变量命名规则1.必须以字母或者下划线_开头2.命名可由字母,数字或下划线组成3.大小写敏感4.尽量避免使......
  • 聪明办法学python
    条件:if 表达式:        行动      elif 表达式:         行动      else:          行动match状态:      casexx:           行动     caseyy......
  • 【Python】 多层级嵌套循环
    1.渲染多级菜单,并调整数据#生成菜单树状目录classMenuTreeView(APIView):#多层级生成树状目录defgenerate_menu_tree(self,parent_menu):temp_menu_list=[]sub_menus=models.Menu.objects.filter(parent=parent_menu)forsu......
  • python批量修改文件名
    需求:有几十个文件(不超过100个),要根据文件名加序号思路:用字典将关键字对应序号,再批量改文件名,代码比较简单:importospath=input("请输入需批量更名的文件夹全路径:")units={"总裁办":"01","生产处":"02","安全处":"03"}files=os.listdir(path)forfilein......
  • 构建树结构(节点级别,全路径)
    packageorg.example.tree;importorg.springframework.util.CollectionUtils;importjava.util.*;/***@ClassNameTreeUtils2*@DescriptionTODO*@Authorhrp*@Date2023/11/2314:39*/publicclassTreeUtils<NextendsTreeNode<T,RC,LC>,......
  • 编程语言和Python语言介绍
    (一)编程语言和Python语言介绍(1)编程语言的分类(1)机器语言什么是机器语言?机器语言是计算机可以理解的语言,是直接操作硬件的语言。就是计算机可以听懂的语言。由于计算机基于电工作,电频有高低电频之分,即高电频和低电频(0和1)计算机可以理解的就是二进制的指令(0/1),所有机器语......
  • python-task3:Data Types and Operators
    常见数据类型整数Integer(int)浮点数Float(python中默认为双精度浮点型)布尔值Boolean(bool)类型Type(“类型”也是种类型)其他数据类型字符串String(str)、列表List、元组Tuple、集合Set、字典Dictionary(dict,或者可以叫它映射map)、复数ComplexNumber(complex)、函数Func......