leetcode算法之动态规划（一）

• 2021 年 2 月 11 日
• AI
• C/C++/C#

今天来盘一盘 **动态规划 ** 这类题目

这是最让我头疼的一类题目，一直不想做这类题目，这里开始学习一下。

使用python刷题分类整理的笔记,请参考: //github.com/lxztju/leetcode-algorithm/tree/v1

动态规划

动规就是以空间换取时间。

动态规划常常适用于有重叠子问题和最优子结构性质的问题。

一些思考的套路： 递归 （自顶向下）——> 记忆化递归（自顶向下消除重复） ——> 动态规划（自底而上）

1. 斐波那契数列

• 70 爬楼梯（easy）
• 198 打家劫舍（easy）
• 213 打家劫舍 II（medium）

2. 矩阵路径

• 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];
    }
};

更多分类刷题资料

• 微信公众号： 小哲AI

  

• GitHub地址： //github.com/lxztju/leetcode-algorithm

• csdn博客： //blog.csdn.net/lxztju

• 知乎专栏： //www.zhihu.com/column/c_1101089619118026752

• AI研习社专栏：//www.yanxishe.com/column/109