【leetcode30】

作者

63. 不同路径 II

  1. class Solution:
  2.     def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
  3.         dp=[[0 for _ in range(len(obstacleGrid[0])+1)] for _ in range(len(obstacleGrid)+1)]
  4.         flag=[[True for _ in range(len(obstacleGrid[0])+1)] for _ in range(len(obstacleGrid)+1)]
  5.         for i in range(len(obstacleGrid)):
  6.             for j in range(len(obstacleGrid[0])):
  7.                 if obstacleGrid[i][j]==1:
  8.                     dp[i][j]=0
  9.                     flag[i][j]=False
  10.         for i in range(len(obstacleGrid[0])):
  11.             if flag[0][i]==False:
  12.                 break
  13.             dp[0][i]=1
  14.         for i in range(len(obstacleGrid)):
  15.             if flag[i][0]==False:
  16.                 break
  17.             dp[i][0]=1
  18.         for i in range(1,len(obstacleGrid)):
  19.             for j in range(1,len(obstacleGrid[0])):
  20.                 if flag[i][j]==False:
  21.                     dp[i][j]=0
  22.                 elif flag[i-1][j] and flag[i][j-1]:
  23.                     dp[i][j]=dp[i-1][j]+dp[i][j-1]
  24.                 elif flag[i-1][j]==False and flag[i][j-1]:
  25.                     dp[i][j]=dp[i][j-1]
  26.                 elif flag[i-1][j] and  flag[i][j-1]==False:
  27.                     dp[i][j]=dp[i-1][j]
  28.                 else:
  29.                     dp[i][j]=0
  30.         return dp[len(obstacleGrid)-1][len(obstacleGrid[0])-1]

卡了半天，突然想起来

马兰过河卒 - Gzz's space (guanzhongzheng.online)

于是就过了

343. 整数拆分

  1. class Solution:
  2.     def integerBreak(self, n: int) -> int:
  3.         dp=[0]*(n+1)
  4.         dp[2]=1
  5.         for i in range(3,n+1):
  6.             for j in range(0,i//2+1):
  7.                 dp[i]=max(j*(i-j),j*dp[i-j],dp[i])
  8.         return dp[n]
1.dp[0],dp[1]无意义。题目要求乘积最大，初始化为0，不影响题解
2.for j in range(0,i//2+1):基本不等式，拆两个的情况相等乘积最大，拆多个更不肯接近i//2+1,i//2则错误
3.j*(i-j)拆一个，j*dp[i-j]拆多个，因为有for循环所以也要和之前的dp[i]比较

发表评论