目录
任务
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
思路
经典的DP问题,注意返回值和遍历区间。dp[i][j]表示按照规则到达i,j这个格子的方法数
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * n for i in range(m)]
for j in range(n):
dp[0][j] = 1
for i in range(m):
dp[i][0] = 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
思路
与上题基本一致，加了障碍即障碍的格子无法到达，方法数为0，此外初始化时，一旦发现了障碍的格子，则遍历第一行（列）时，其后的格子均无法到达
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0]) if m>0 else 0
dp = [[0] * n for i in range(m)]
for j in range(n):
if obstacleGrid[0][j] == 1:
break
dp[0][j] = 1
for i in range(m):
if obstacleGrid[i][0] == 1:
break
dp[i][0] = 1
for i in range(1,m):
for j in range(1,n):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i-1][j]+ dp[i][j-1]
return dp[m-1][n-1]
343. 整数拆分
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
思路
dp[i]表示将i拆分成k个正整数（k>=2）并使得乘积最大的乘积值，整体上它有两种取法（实际可以细分），一种是拆成2个数，则结果为j （i-j） ( 实际上拆成两个数也有很多取法，j从1取到i,可剪枝），一种是拆成3个及以上的数，即结果为 jdp[i-j]。然后从中取最大的，由于实际细分（不管是拆成两个数还是拆成更多的数）有很多取法（结合遍历），所以max要在遍历中取最大，即要和dp[i]比较，来保证是遍历中最大的数。
class Solution:
def integerBreak(self, n: int) -> int:
dp = [0] * (n+1)
dp[2] = 1
for i in range(3,n+1):
#for j in range(1,i):
for j in range(1,i//2 +1):
dp[i] = max(dp[i],max((j*(i-j)),j*dp[i-j]))
return dp[n]
96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
思路
dp[i]表示 有i个节点的二叉搜索树构成一共有的种数，它是 左子树的种数 * 右子树的种数累计起来的。
如，当i = 3， 它是左子树为0个节点，右子树为2个节点 的种类，加上左右子树都是一个节点的种类 + 左子树2个节点，右子树0个节点的种类，即
dp[3] = dp[0]dp[2]+dp[1]dp[1] + dp[2]*dp[0]
因此，通用的，用j表示左子树节点的个数，它最小是0，最大是i-1（因为根占掉一个节点），那么右子树节点的个数就是i-j-1。
class Solution:
def numTrees(self, n: int) -> int:
if n == 1: return 1
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
for i in range(2,n+1):
for j in range(0,i):
dp[i] += dp[j] * dp[i-j-1]
return dp[n]