leetcode演算法之動態規劃（一）

今天來盤一盤 **動態規劃 ** 這類題目

這是最讓我頭疼的一類題目，一直不想做這類題目，這裡開始學習一下。

使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1

動態規劃

動規就是以空間換取時間。

動態規劃常常適用於有重疊子問題和最優子結構性質的問題。

一些思考的套路： 遞歸 （自頂向下）——> 記憶化遞歸（自頂向下消除重複） ——> 動態規劃（自底而上）

  1. 斐波那契數列
  • 70 爬樓梯（easy）
  • 198 打家劫舍（easy）
  • 213 打家劫舍 II（medium）
  1. 矩陣路徑
  • 64 最小路徑和（medium）
  • 62 不同路徑（medium）

1. 斐波那契數列

這類題目是斐波那契數列是最簡單的動態規劃的問題，對於這類題目，我會首先使用遞歸直觀解決問題， 然後利用記憶化遞歸的方法去重，最後使用動態規劃實現自底而上的方法。

70 爬樓梯（easy）

  • 遞歸
  • n-1到n有一種方法，第n-2到n有1種方法。
  • 因此到達第n階樓梯的方法為到達第n-1階的方法與第n-2階樓梯的方法和
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        return climbStairs(n-1) + climbStairs(n-2);
    }
};
  • 記憶化遞歸
  • 因為在上述遞歸方法種
  • 例如要求 f(10) = f(9) + f(8)，就要求f(9)與f(8)
    f(9) = f(8) + f(7)
    f(8) = f(7) + f(6)
    從上邊的分析，可以看出存在大量的重複計算，隨著所求數字的增大，重複計算大量的增加，這裡採用map來存儲已經計算過的元素，例如在求f(9)時f(8)保存下來，然後遇到求f(8)的位置，不進行往下計算，實現遞歸樹的剪枝
class Solution {
public:
    unordered_map<int, int> memo;
    int climbStairs(int n) {
        if (n <= 2) return n;
        if (memo.find(n) == memo.end())
            memo.insert(make_pair(n, climbStairs(n-1) + climbStairs(n-2)));
        
        return memo[n];
    }
};
  • 記憶化遞歸時自上而下的方法， 動態規劃是自下而上的方法
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i< n+1; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

198 打家劫舍（easy）

  • 遞歸
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        return helper(nums.size() - 1, nums);
    }
    int helper(int n, vector<int>& nums){
        if (n == 0) return nums[0];
        if (n == 1) return max(nums[0], nums[1]);
        // 偷盜第n-1房，與偷盜n房的最值
        return max(helper(n-1, nums), helper(n-2, nums) + nums[n]);
    }
};
  • 記憶化遞歸
class Solution {
public:
    unordered_map<int, int> memo;
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        return helper(nums.size() - 1, nums);
    }
    int helper(int n, vector<int>& nums){
        if (n == 0) return nums[0];
        if (n == 1) return max(nums[0], nums[1]);
        if (memo.find(n-1) == memo.end())
            memo[n-1] = helper(n-1, nums);
        if (memo.find(n-2) == memo.end())
            memo[n-2] = helper(n-2, nums);
        // 偷盜第n-1房，與偷盜n房的最值
        return max(memo[n-1], memo[n-2] + nums[n]);
    }
};
  • 動態規劃
class Solution {
public:
    unordered_map<int, int> memo;
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i< nums.size(); i++){
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.size() - 1];
    }
};

213 打家劫舍 II（medium）

  • 這個題與上一題的主要區別在於這裡的數組是循環的。

  • 直觀的思路可以分為兩種情況，一種是選擇第一間房丟掉最後一間房nums(nums.begin(), nums.end() - 1)，第二種是選擇最後一間房丟掉第一間房nums(nums.begin() + 1, nums.end())。在二者中取得最大值即可

  • 直接採用動態規劃， 懶得用遞歸了

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp1(nums.size() - 1, 0); //丟掉最後一個 
        vector<int> dp2(nums.size() - 1, 0); // 丟掉第一個元素
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);
        dp1[0] = nums[0];
        dp1[1] = max(nums[0], nums[1]);
        dp2[0] = nums[1];
        dp2[1] = max(nums[1], nums[2]);
        for (int i = 2; i< nums.size()-1; i++){
            dp1[i] = max(dp1[i-1], dp1[i-2] + nums[i]);
            dp2[i] = max(dp2[i-1], dp2[i-2] + nums[i+1]);
        }
        return max(dp1[nums.size()-2], dp2[nums.size()-2]);
    }
};

2. 矩陣路徑

這類題目是在一個矩陣中找尋滿足題意的路徑。

依然採用 遞歸-> 記憶化遞歸 -> 動態規劃的三種方法來求解這個問題。

64 最小路徑和（medium）

  • 遞歸
  • 假設f(i,j)為從起始位置到i， j位置的最小路徑和，從上邊和左邊兩個方向可以到達i j 。
  • 因此f(i,j) = min( f(i-1, j), f(i, j-1) ) + grid[i][j]
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        return pathsum(m-1, n-1, grid);
    }
    int pathsum(int i, int j, vector<vector<int>>& grid){
        if (i == 0 && j == 0) return grid[0][0];
        int left = i-1 >= 0 ? pathsum(i-1, j, grid) : INT_MAX;
        int up = j-1 >= 0 ? pathsum(i, j-1, grid) : INT_MAX;
        return min(left, up) + grid[i][j];
    }
};
  • 記憶化遞歸
  • 可以直觀看出存在大量的重複運算，採用記憶化數組來消除重複計算
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> memo(m, vector<int>(n, -1));
        return pathsum(m - 1, n - 1, grid, memo);
    }

    int pathsum(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& memo){
        if (i == 0 && j == 0) return grid[0][0];

        int left = INT_MAX;
        if (i - 1 >= 0){
            if (memo[i-1][j] == -1)
                memo[i-1][j] = pathsum(i-1, j, grid, memo);
            left = memo[i-1][j];
        }

        int up = INT_MAX;
        if (j - 1 >= 0){
            if (memo[i][j - 1] == -1)
                memo[i][j - 1] = pathsum(i, j - 1, grid, memo);
            up = memo[i][j-1];
        }
        return min(left, up) + grid[i][j];
    }
};
  • 動態規劃： 自底而上
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(grid); // dp[i][j]表示從起始點達到ij的最小的路徑和。
        for (int i = 1; i< m; i++){
            dp[i][0] +=dp[i-1][0];
        }
        for (int j = 1; j < n; j++){
            dp[0][j] += dp[0][j-1];
        }
        for (int i = 1; i< m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

62 不同路徑（medium）

  • 直接使用動態規劃
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 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];
    }
};

更多分類刷題資料

Tags:

VirMach 便宜 VPS