資料結構與算法·動态規劃 (一) (Dynamic Programming)

Dynamic Programming

文章目錄

• Dynamic Programming
• 一，動态規劃題目的特點
• 二，動态規劃解題步驟
• 三，習題練習

一，動态規劃題目的特點

• 計數型
  • 有多少種方式走到右下角
  • 有多少種方法選出K個數使得和是Sum
• 求最大，最小值
  • 從左上角走到右下角路徑的最大數字和
  • 最長上升子序列長度
• 求存在性
  • 取石子遊戲，先取是否必勝
  • 能不能選出K 個數使得和是Sum

二，動态規劃解題步驟

• 确定狀态
  • 數組中的每個元素dp[i]或者dp[i][j]代表什麼；數組需要開多大，是否需要加一。
  • 确定最後一步和子問題（問 題一樣，規模變小）
• 确定轉移方程
• 确定初始條件和邊界情況（用轉移方程算不出來的，沒有意義的，需要手動定義；邊界情況：注意不要數組越界）
• 計算順序（一般為從小到大，從上到下，從左到右）

三，習題練習

(1), 給定不同面額的硬币 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬币個數。如果沒有任何一種硬币組合能組成總金額，傳回 -1。你可以認為每種硬币的數量是無限的。

代碼如下（示例）：

public int coinNumber(int[] A, int B){
         //0~n: n+1
         int[] f = new int[B+1];
         int n = A.length; //number of the available coins.
         
         //initialization
         f[0]=0;
         for(int i=1; i<=B; i++) {
             //先假設都拼不出來
             f[i]=Integer.MAX_VALUE;
             //last coin A[j]
             //f[j] = min{f[i-A[0]+1,~f[i-A[n]+1}
             for(int j=0; j<n; j++) {
                 //無窮大+1會造成越界，也就是拼不出來（i-A[j]）
                 if(i-A[j]>=0 && f[i-A[j]]!=Integer.MAX_VALUE) {
                     f[i]=Math.min(f[i], f[i-A[j]]+1);
                 }
             }
         }
         
         if(f[B]==Integer.MAX_VALUE) {
             return -1;
         }
         
         return f[B];
     }
           

(2), 一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中标記為“Start” ）。機器人每次隻能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中标記為“Finish”）。問總共有多少條不同的路徑？

public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0 || j==0){
                    dp[i][j]=1;
                }else{
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
           

(3), 跳躍遊戲

給定一個非負整數數組，你最初位于數組的第一個位置。數組中的每個元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達最後一個位置。

class Solution {
    public boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0]=true;


        for(int i=1; i<nums.length; i++){
            dp[i]=false;
            for(int j=0; j<i; j++){
                if(dp[j] && nums[j]+j>=i){
                    dp[i]=true;
                    break;
                }
            }


        }
        return dp[nums.length-1];
    }
}
           

(4), 跳躍遊戲 II 給定一個非負整數數組，你最初位于數組的第一個位置。數組中的每個元素代表你在該位置可以跳躍的最大長度。你的目标是使用最少的跳躍次數到達數組的最後一個位置。

int length = nums.length;
        int end = 0;
        int maxPosition = 0; 
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]); 
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;