🔥 個人主頁: 黑洞曉威
😀你不必等到非常厲害，才敢開始，你需要開始，才會變的非常厲害

343. 整數(shù)拆分

給定一個正整數(shù) n ，將其拆分為 k 個 正整數(shù) 的和（ k >= 2 ），并使這些整數(shù)的乘積最大化。

返回 你可以獲得的最大乘積 。

解題思路

這個問題可以使用動態(tài)規(guī)劃來解決。我們定義一個數(shù)組 dp，其中 dp[i] 表示將正整數(shù) i 拆分后可以獲得的最大乘積。

首先，我們初始化 dp[1] = 1，因為任何數(shù)拆分成兩個數(shù)的乘積最小值為 1 * 1 = 1。

然后，我們從正整數(shù) 2 開始，依次計算 dp 數(shù)組的值。對于每個正整數(shù) i，我們通過迭代 j（j 的范圍是從 1 到 i - 1）來計算 dp[i]。對于每個 j，我們計算兩種情況下的最大值：

1. j * (i - j)：將 i 拆分成 j 和 i - j 兩個數(shù)相乘的結(jié)果。
2. j * dp[i - j]：將 i 拆分成 j 和 dp[i - j] 兩個數(shù)相乘的結(jié)果。

代碼實現(xiàn)

class Solution {public int integerBreak(int n) {int[] dp = new int[n + 1];dp[1] = 1; // 初始化 dp[1]for (int i = 2; i <= n; i++) {for (int j = 1; j < i; j++) {dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));}}return dp[n];}
}

63. 不同路徑 II

一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標記為 “Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為 “Finish”）。

現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？

網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示

解題思路

我們可以定義一個二維數(shù)組 dp，其中 dp[i][j] 表示從起始點到達網(wǎng)格的位置 (i, j) 的不同路徑數(shù)。根據(jù)題目要求，如果某個位置有障礙物，那么該位置的路徑數(shù)為 0。

接下來，我們可以根據(jù)動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程來計算 dp 數(shù)組。狀態(tài)轉(zhuǎn)移方程如下：

• 如果當前位置 (i, j) 是障礙物（obstacleGrid[i][j] == 1），那么 dp[i][j] = 0；
• 否則，dp[i][j] = dp[i-1][j] + dp[i][j-1]，即當前位置的路徑數(shù)等于上方和左方位置的路徑數(shù)之和。

最終，dp[m-1][n-1] 即為從起始點到達右下角的不同路徑數(shù)。

代碼實現(xiàn)

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];// 初始化起始點dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;// 初始化第一列for (int i = 1; i < m; i++) {dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i-1][0];}// 初始化第一行for (int j = 1; j < n; j++) {dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j-1];}// 計算其余位置的路徑數(shù)for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
}