今天是動(dòng)態(tài)規(guī)劃的第二天隘马！今天稍微加點(diǎn)難度太防，不僅有涉及二維數(shù)組，還有涉及 有難度的思考遞推公式的題酸员！
題目鏈接：62. 不同路徑
狀態(tài)：思路不難蜒车，套用模版，直接AC幔嗦。
在上一篇中酿愧，爬樓梯題目中，我學(xué)會(huì)了當(dāng)一次可以爬1階或2階樓梯時(shí)邀泉，那么 到達(dá)第n層樓梯的方法數(shù) = 到達(dá)第n-1層樓梯的方法數(shù) + 到達(dá)第n-2層樓梯的方法數(shù)嬉挡。這是因?yàn)?可以看成從第n-1階爬1階到達(dá) 或 從n-2階爬2階到達(dá)。
相同的道理汇恤，到達(dá)第[i][j]格時(shí)的方法總數(shù) = 到達(dá)第[i-1][j]格時(shí)的方法總數(shù) + 到達(dá)第[i][j-1]格時(shí)的方法總數(shù)庞钢。因?yàn)榭梢钥闯墒?到達(dá)第[i-1][j]格時(shí) 向右走一格 或 到達(dá)第[i][j-1]格時(shí) 向下走一格。
動(dòng)態(tài)規(guī)劃五部曲：
- dp[i][j] 表示 到達(dá)[i][j]格時(shí)的方法總數(shù)
- 遞推公式 上述提過因谎。因此dp[i][j] = dp[i-1][j] + dp[i][j-1]
- 初始化基括。第一行和第一列都要為1。因?yàn)橹挥?橫著一直向右/豎著一直向下 這一種方法可以到達(dá)第一行/第一列的格子
- 遍歷财岔。從左向右风皿，從上到下的遍歷。這是因?yàn)轭}目的基調(diào)就是機(jī)器人從左上往右下走匠璧，且機(jī)器人只能右移或下移
- 想測(cè)試的話可以打印桐款。
綜上所述，完整代碼如下:
class Solution: // Python
def uniquePaths(self, m: int, n: int) -> int:
# Create a two-dimensional list to store the number of unique paths
dp = [[0] * n for _ in range(m)]
#initialization
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
# Count the number of unique paths to each cell
for i in range(1,m):
for j in range(1,n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Returns the number of unique paths to the bottom right cell
return dp[m-1][n-1]
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(mn). 初始化是O(m)+O(n)夷恍， 但是兩層for循環(huán)遍歷每個(gè)格子的時(shí)候是O(mn)
空間復(fù)雜度：O(mn). 用了一個(gè)mn的二維列表
題目鏈接：63. 不同路徑 II
狀態(tài)：核心思路不變魔眨，套用模版，直接AC。
本題核心思路不變冰沙，只是需要處理一下遇到障礙物的情況侨艾。
- 如果開頭或結(jié)尾為障礙物，則從開始走到結(jié)果的可能性為0
- 如果第一行/第一列有障礙物拓挥，則從 第一行的障礙物往右/第一列障礙物往下 都是走不到的地方了，因此這些走不到的地方的初始化為0袋励，走得到的 初始化還是為1
- 遍歷中遇到中間的障礙物了侥啤，直接continue到下一次循環(huán)就好
動(dòng)態(tài)規(guī)劃五部曲同上。三種遇到障礙物的情況分別對(duì)應(yīng)了開頭的判斷茬故、初始化的處理盖灸、以及循環(huán)時(shí)的處理。
綜上所述磺芭，完整代碼如下:
class Solution: // Python
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid) # Number of grid rows
n = len(obstacleGrid[0]) # Number of columns in the grid
# If there is an obstacle at the start or end point, return 0 directly
if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
return 0
# Create a two-dimensional list to store the path number
dp = [[0] * n for _ in range(m)]
# initialization
# When encountering an obstacle, exit the loop directly, and the default value is 0.
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
# Core logic: Calculate the number of paths to other locations
for i in range(1,m):
for j in range(1,n):
if obstacleGrid[i][j] == 1:
continue
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
復(fù)雜度分析同上赁炎。
題目鏈接：343. 整數(shù)拆分
狀態(tài)：分析好五部曲之后，一次性AC并不難钾腺！
動(dòng)態(tài)規(guī)劃五部曲：
- dp[i]徙垫。 數(shù)字為i時(shí)，dp[i]表示拆分?jǐn)?shù)字i所獲的最大乘積放棒。
- 遞推公式姻报。在拆分過程中，有兩種情況：一间螟、把i拆分成j與i-j兩個(gè)數(shù)吴旋。二、把i-j繼續(xù)拆分厢破。因此兩種情況的乘積結(jié)果分別表示為 j * (i-j)荣瑟、j * dp[i-j]。因此摩泪，在遍歷過程中取最大值就好笆焰，但是別忘了取最大值的時(shí)候還要帶上dp[i]本身。
- 初始化加勤。dp[0]和dp[1]根本沒意義仙辟，所以不管。dp[2]只有一種拆法且結(jié)果為1所以就把dp[2]初始化為1就好了鳄梅。
- 遍歷叠国。從小到大遍歷，因?yàn)楹竺娴闹狄蕾嚽懊娴慕Y(jié)果戴尸。
- 想測(cè)試的話可以打印粟焊。
綜上所述，完整代碼如下：
class Solution: // Python
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, n // 2 + 1):
dp[i] = max(dp[i], j * (i - j), j * dp[i-j])
return dp[n]
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(n ^ 2). 兩層for循環(huán)就是n^2了
空間復(fù)雜度：O(n). 大小為n+1的數(shù)組
