/** 動態規劃專題：這是最簡單的并且已經給出了轉移方程，平時我們用dp[]數組來表示轉移方程轉移方程： dp[n] = dp[n-1]+dp[n-2]初始值：dp[0] = 0 , dp[1] = 1*/ class Solution {public int fib(int n) {if(n ==0)return 0;int[] dp = new int[n+1];dp[0] = 0;dp[1] = 1;for(int i=2 ; i<=n ; i++){dp[i] = dp[i-1] + dp[i-2]; }return dp[n];} } /** 上題的空間復雜度太高了，因此我們可以換一種寫法，不需要dp，其實下面這種寫法有點像遞歸,但是時間復雜度下來了，并且遞歸用的數據結構是"棧"*/class Solution {public int fib(int n) {if(n<2){return n;}return fib(n-1)+fib(n-2);} }

/** 動態規劃：一次可以爬1~2個臺階：因此轉移方程：dp[n] = dp[n-1] + dp[n-2] ,初始值 dp[0] =1 , dp[1] =1 , 對于dp[0]其實我們不知道登于0還是1，但是我們可以通過dp[2]去遞推，dp[2]應該等于2，因此dp[0]應該等于1*/ class Solution {public int climbStairs(int n) {if(n < 2)return 1;int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for(int i=2 ; i<=n ; i++){dp[i] = dp[i-2] + dp[i-1];}return dp[n];} }

/** 動態思想：該題基礎也是爬樓梯問題，只不過我們要記錄的是花費的值：轉移方程：dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])、初始值：dp[0] = 0 , dp[1] = 0 , dp[2] = Math.min(dp[0]+cost[0] ,dp[1]+cost[1])*/ class Solution {public int minCostClimbingStairs(int[] cost) {//cost范圍已經給出>=2，因此不用進行判別<2的情況int len = cost.length;int[] dp = new int[len+1];dp[0] =0;dp[1] =0;for(int i=2 ; i<=len ; i++){dp[i] = Math.min(dp[i-2]+cost[i-2] , dp[i-1]+cost[i-1]);}return dp[len];} }

dsadas

/** 動態規劃：其實我們發現對于動態規劃，就是求什么就設什么，因為這是一個網格，因此dp[m][n]表示一個網格，并且因只能向下或向右移動，因此：轉移方程 ：dp[m][n] = dp[m][n-1] + dp[m-1][n];初始值：因為是二維，所以初始值是兩個邊 dp[i][0] , dp[0][j] dp[i][0]1 , dp[0][j] = 1 , dp[0][0] =1;*/ class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];//初始值dp[0][0] = 1;for(int i=1 ; i<m ; i++){dp[i][0] = 1;}for(int j=1 ; j<n ; j++){dp[0][j] = 1;}//轉移方程for(int i=1 ; i<m ; i++){for(int j=1 ; j<n ; j++){dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];} }// 我們求表達式，從初始點到結尾一共要走移動m+n-2次，我們要在其中m-1次向下 // 也就是一共(m+n-2)!/[(m-1)!*(n-1)!]=(m+n-2)*(m+n-3)*...*n/(m-1)! 不推薦 // class Solution { // public int uniquePaths(int m, int n) { // long res = 1; // for(int x=1 , y=n ; x<m ; x++,y++){ //注意用long ,要不然可能溢出 // res = res*y/x; //這里還不能寫成 res*(y/x)，因此可能除不開 // } // return (int)res; // } // }

ssdadsad

/** 動態規劃：相對于 “不同路徑” 這道題 ， 該題添加了額外的障礙物， 用"1"表示思考：因為只能向下或者向右走，因此我們需要注意的是障礙物的下面和右邊一個格：轉移方程依舊要分情況：對于dp[m][n]1、obstacleGrid[m][n] == 0 , 則 dp[m][n] = 02、obstacleGrid[m][n] ≠ 0 ， 則dp[m][n] = dp[m-1][n] + dp[m][n-1];*/ class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];//初始值for(int i=0 ; i<m ; i++){if(obstacleGrid[i][0] == 1)break;elsedp[i][0] = 1; //說明遇到障礙了，則后面為0}for(int j=0 ; j<n ; j++){ //必須j==0開始，避免障礙物在開頭，那樣如果j==1開始，則dp[0][j] =1會錯誤if(obstacleGrid[0][j] == 1) break;else dp[0][j] = 1;}//寫轉移方程for(int i=1 ; i<m ; i++){for(int j=1; j<n ; j++){if(obstacleGrid[i][j] == 1)dp[i][j] = 0;elsedp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];} }

/** 解題思想：這道題我沒有想到用動態規劃,一開始沒什么思路，注意 2<=n<=58動態規劃：求什么設什么 dp[n]表示為可以獲得的最大值 ，n開始分成不同值得和，因此我們可以遍歷數組，轉移方程直接寫*/ class Solution {public int integerBreak(int n) {int[] dp = new int[n+1];//初始值dp[0] = 0;dp[1] = 0;for(int i=2 ; i<=n ; i++){//對dp[i]分成不同得值得和，求其最大乘積for(int j=1 ; j<i ; j++){dp[i] = Math.max(j*dp[i-j],Math.max(j*(i-j), dp[i]));}}return dp[n];} }

//動態規劃：動態規劃的思想就是解決一個一個的小問題，然后合成一個大問題，因此比如給定一個有序序列1~n，我們可以i(2~n)為樹根，將1~(i-1)序列作為左子樹，將(i+1)~n作為右子樹。接著我們可以按照同樣的方式遞歸構建左子樹和右子樹。 //說到動態規劃：兩個步驟：1、邊界條件 2、轉移方程 //定義兩個函數：G(n),長度為n的序列能構成的不同二叉搜索樹的個數,且G(0)=1,G(1)=1 //F(i.n):以i為根，序列長度為n的不同二叉樹搜索個數(1<=i<=n) G(n) = F(i,n)的累加和，i為1~n，F(i,n) = G[i-1]*G[n-i] class Solution {public int numTrees(int n) {int[] dp = new int[n+1];//邊界條件dp[0] = 1;dp[1] = 1;//n為2及以上的二叉搜索樹的個數for(int i=2 ; i<=n ; i++){//我們以j為根節點，for(int j=0 ; j<i ; j++){dp[i] += dp[j]*dp[i-1-j];}}return dp[n];} }

總結

以上是生活随笔為你收集整理的【力扣动态规划基础专题】：509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯 62. 不同路径 63. 不同路径 II 343. 整数拆分 96. 不同的二叉搜索树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。