動態規劃

動規五部曲：

1. 確定dp數組以及下標的含義
2. 確定遞推公式
3. dp數組如何初始化
4. 確定遍歷順序
5. 舉例推導dp數組

70. 爬樓梯 - 力扣（LeetCode）

爬到第一層樓梯有一種方法，爬到二層樓梯有兩種方法。

那么第一層樓梯再跨兩步就到第三層 ，第二層樓梯再跨一步就到第三層。

所以到第三層樓梯的狀態可以由第二層樓梯 和 到第一層樓梯狀態推導出來，那么就可以想到動態規劃了。

我們來分析一下，動規五部曲：

定義一個一維數組來記錄不同樓層的狀態

1. 確定dp數組以及下標的含義

dp[i]： 爬到第i層樓梯，有dp[i]種方法

1. 確定遞推公式

如何可以推出dp[i]呢？

從dp[i]的定義可以看出，dp[i] 可以有兩個方向推出來。

首先是dp[i - 1]，上i-1層樓梯，有dp[i - 1]種方法，那么再一步跳一個臺階不就是dp[i]了么。

還有就是dp[i - 2]，上i-2層樓梯，有dp[i - 2]種方法，那么再一步跳兩個臺階不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]與dp[i - 2]之和！

所以dp[i] = dp[i - 1] + dp[i - 2] 。

在推導dp[i]的時候，一定要時刻想著dp[i]的定義，否則容易跑偏。

class Solution {public int climbStairs(int n) {if(n==1||n==2) return n;int[] dp=new int[n+1];dp[0]=1;dp[1]=1;//dp[2]應該是2dp[2]=2;for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
}

746. 使用最小花費爬樓梯 - 力扣（LeetCode）

題目沒說明白，腦殘的很

class Solution {public int minCostClimbingStairs(int[] cost) {//這個題他爹的有毛病 cost的長度是n 但是樓梯下標要到n 長度為n+1 if(cost.length==2) return Math.min(cost[0],cost[1]);//只有1極樓梯int n=cost.length;//dp表示到達此處的最小花費int[] dp=new int[n+1];dp[0]=0;dp[1]=0;//因為可以選擇從0或者1出發for(int i=2;i<=n;i++){dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[n];}
}

?63. 不同路徑 II - 力扣（LeetCode）

和62不同路徑一樣 先初始化橫豎兩排，然后判斷一下有障礙的地方dp就是0

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m=obstacleGrid.length;int n=obstacleGrid[0].length;int[][] dp=new int[m][n];//如果第一行或第一列中存在障礙物，那么障礙物之后的路徑數量應該是0，而不是1。for(int i=0;i<obstacleGrid.length;i++){if(obstacleGrid[i][0]==0){dp[i][0]=1;}else{break;}}for(int j=0;j<obstacleGrid[0].length;j++){if(obstacleGrid[0][j]==0){dp[0][j]=1;}else{break;}}for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j]!=1){dp[i][j]=dp[i-1][j]+dp[i][j-1];}else{dp[i][j]=0;}}}return dp[m-1][n-1];}
}

?

?118. 楊輝三角 - 力扣（LeetCode）

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> res=new ArrayList<>();res.add(List.of(1));for(int i=1;i<numRows;i++){List<Integer> row=new ArrayList<>(i+1);//i+1是元素數量//第一個是1row.add(1);for (int j = 1; j < i; j++) {// 左上方的數 + 正上方的數row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));}//最后一豎是1row.add(1);res.add(row);}return res;}
}

**343. 整數拆分 - 力扣（LeetCode）?

class Solution {public int integerBreak(int n) {//dp[i] 為正整數 i 拆分后的結果的最大乘積int[] dp = new int[n+1];dp[1]=1;dp[2]=1;for(int i = 3; i <= n; i++) {for(int j = 1; j < i;j++) {//如果在比較最大值的時候不包括dp[i]，那有可能越比越小，倒把一開始找到的最大值給弄丟了dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));// j * (i - j) 是單純的把整數 i 拆分為兩個數 也就是 i,i-j ，再相乘//而j * dp[i - j]是將 i 拆分成兩個以及兩個以上的個數,再相乘。}}return dp[n];}
}

?

?198. 打家劫舍 - 力扣（LeetCode）

動態規劃的的四個解題步驟是：

• 定義子問題
• 寫出子問題的遞推關系
• 確定 DP 數組的計算順序
• 空間優化（可選）

class Solution {public int rob(int[] nums) {if(nums.length==1) return nums[0];if(nums.length==2) return Math.max(nums[0],nums[1]);//只有兩種狀態 偷竊或者不偷竊int[] dp=new int[nums.length];//表示兩種狀態中最大獲利dp[0]=nums[0];//    dp[1]=nums[1];不對哦dp[1]=Math.max(dp[0],nums[1]);//列出狀態轉移方程for(int i=2;i<nums.length;i++){dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);}return dp[nums.length-1];}
}

首先「完全平方數」有無限個，但要湊成的數字是給定的。

所以首先把所有可能用到的「物品」預處理出來。

從而將問題轉換為：給定了若干個數字，每個數字可以被使用無限次，求湊出目標值n所需要用到的是最少數字個數是多少。

152. 乘積最大子數組 - 力扣（LeetCode）

class Solution {public int maxProduct(int[] nums) {int max = Integer.MIN_VALUE, imax = 1, imin = 1;for(int i=0; i<nums.length; i++){if(nums[i] < 0){ 
//由于存在負數，那么會導致最大的變最小的，最小的變最大的。因此還需要維護當前最小值imin 
//在出現負數這種危機關頭計算最大最小int tmp = imax;imax = imin;imin = tmp;}imax = Math.max(imax*nums[i], nums[i]);//一旦前面有負數就放棄曾經的一切imin = Math.min(imin*nums[i], nums[i]);max = Math.max(max, imax);}return max;}
}