動態(tài)規(guī)劃

解題固定步驟

一般，只要解決問題的階段、狀態(tài)和狀態(tài)轉移決策確定了，就可以寫出狀態(tài)轉移方程（包括邊界條件）。
根據動態(tài)規(guī)劃的三大基本要素可以設計解題步驟如下：

• 狀態(tài)定義： 每個狀態(tài)的決策，存放每個狀態(tài)的變量，

• 狀態(tài)轉移方程： 當前狀態(tài)與上一個狀態(tài)之間的關系

• 初始狀態(tài)： 初始的狀態(tài)或者邊界條件

  不太熟動態(tài)規(guī)劃的話一定要在草稿紙上寫出初始狀態(tài)，然后再慢慢遞推，找出狀態(tài)轉移方程。

  套路寫多了就會了

198. 打家劫舍

198. 打家劫舍 題目鏈接

你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之內能夠偷竊到的最高金額。

class Solution {
    public int rob(int[] nums) {
        int k=0;
        int[] dp=new int[nums.length];
        dp[0]=nums[0]; //基本條件
        if(nums.length==1)
        {
            return dp[0];
        }
        dp[1]=Math.max(nums[0],nums[1]);//基本條件
        if(nums.length==2)
        {
            return dp[1];
        }

        for(int i=2;i<nums.length;i++)
        {
            //動態(tài)轉移方程
            //第一種情況：不偷當前房屋，還是前一個房屋的最大值
            //第二種情況：偷當前房屋，再加上前兩個房屋的最大值
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
            									
        }
        return dp[nums.length-1];
    }
}

213. 打家劫舍 II

213. 打家劫舍 II 題目鏈接

你是一個專業(yè)的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警 。

給定一個代表每個房屋存放金額的非負整數數組，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。

解題思路

? 這題比上一題多了個環(huán)型條件，為了方便起見，把環(huán)型問題轉化成兩個直線問題，最后比較出結果

class Solution {
    public int rob(int[] nums) {
        if(nums.length==1)
        {
            return nums[0];
        }else if(nums.length==2)
        {
            return Math.max(nums[0],nums[1]);
        }
        //把環(huán)型問題轉化成兩個直線問題
        int[] dp1=new int[nums.length-1]; //不包含尾
        int[] dp2=new int[nums.length];  //不包含頭
        //基本條件
        dp1[0]=nums[0];
        dp1[1]=Math.max(nums[0],nums[1]);

        for(int i=2;i<nums.length-1;i++)
        {
            dp1[i]=Math.max(dp1[i-1],dp1[i-2]+nums[i]);
        }

        dp2[0]=0;
        dp2[1]=nums[1];
        dp2[2]=Math.max(nums[1],nums[2]);

        for(int i=3;i<nums.length;i++)
        {
            dp2[i]=Math.max(dp2[i-1],dp2[i-2]+nums[i]);
        }
        int m=Math.max(dp1[nums.length-2],dp2[nums.length-1]);
        return m;
    }
}

121. 買賣股票的最佳時機

121. 買賣股票的最佳時機 題目鏈接

給定一個數組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票。設計一個算法來計算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int[] dp1=new int[n]; //前i天買入最小值
        int[] dp2=new int[n];  //前i天收入最大值
        //基本條件
        dp1[0]=prices[0];
        dp2[0]=0;
        for(int i=1;i<n;i++)
        {
            dp1[i]=Math.min(dp1[i-1],prices[i]);
            dp2[i]=Math.max(dp2[i-1],prices[i]-dp1[i-1]);
        }
        return dp2[n-1];
    }
}

746. 使用最小花費爬樓梯

746. 使用最小花費爬樓梯 題目鏈接

給你一個整數數組 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個臺階。

你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。

請你計算并返回達到樓梯頂部的最低花費。

示例 1：

輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋：因為路徑 1→3→1→1→1 的總和最小。

解題思路

題目說可以從下標0或者下標1開始，為了方便起見，我用了兩個dp數組，dp[]從樓梯0開始，dp1[]從樓梯1開始。

最后比較兩種哪個花費小，得出結果

class Solution {
    public int minCostClimbingStairs(int[] cost) {
          int n=cost.length+1;//+1的原因是，題目就要求走到樓梯頂部，而不是最后一個樓梯
          int[] dp=new int[n];
          //初始狀態(tài)
          dp[0]=0;
          dp[1]=cost[0];
          for(int i=2;i<n;i++)
          {
              
              dp[i]=Math.min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2]);
          }
          
          int[] dp1=new int[n];
          //初始狀態(tài)
          dp1[0]=0;
          dp1[1]=0;
          dp1[2]=cost[1];

          for(int i=3;i<n;i++)
          {
              dp1[i]=Math.min(cost[i-1]+dp1[i-1],cost[i-2]+dp1[i-2]);
          }
          if(dp1[n-1]>dp[n-1])
              return dp[n-1];
          else
              return dp1[n-1];
    }
}

64. 最小路徑和

64. 最小路徑和 題目鏈接

給定一個包含非負整數的 *m* x *n* 網格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。

**說明：**每次只能向下或者向右移動一步。

解題思路

第一種情況:在起點，直接等于起點
第二種情況：在最左邊，只能從上面走
第三種情況：在最上面，只能從座邊走
第四種情況:沒有任何邊界，可以從兩個方向走

class Solution {
    public int minPathSum(int[][] grid) {
        int n= grid.length;
        int m= grid[0].length;
        int[][] dp=new int[n][m];

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(i==0 && j==0)//在起點
                {
                    dp[i][j]=grid[i][j];
                }else if(j==0)//在最左邊
                {
                    dp[i][j]=dp[i-1][j]+grid[i][j];
                }else if(i==0)//在最上面
                {
                    dp[i][j]=dp[i][j-1]+grid[i][j];
                }else{//沒有邊界限制
                    dp[i][j]=Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
                }
            }
        }
        return dp[n-1][m-1];
    }
}

后來發(fā)現可以不用創(chuàng)建dp數組，因為每次加完grid之后，就不用了，每個方格的元素只加過一次，所以直接在元素組grid進行操作，具體代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-721367.html

class Solution {
    public int minPathSum(int[][] grid) {
        int n= grid.length;
        int m= grid[0].length;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(i==0 && j==0)//在起點
                {
                    continue;
                }else if(j==0)//在最左邊
                {
                    grid[i][j]=grid[i-1][j]+grid[i][j];
                }else if(i==0)//在最上面
                {
                    grid[i][j]=grid[i][j-1]+grid[i][j];
                }else{//沒有邊界限制
                    grid[i][j]=Math.min(grid[i-1][j]+grid[i][j],grid[i][j-1]+grid[i][j]);
                }
            }
        }
        return grid[n-1][m-1];
    }
}

到了這里，關于力扣：動態(tài)規(guī)劃簡單題集解的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！