LeetCode刷题记录(动态规划篇)

LeetCode刷题记录(动态规划篇),个人向。

[70] Climbing Stairs

难度:Easy
语言:C++

题目描述
i层可以从i - 1层跳一步或者从i - 2层跳两步,所以有dp[i] = dp[i - 1] + dp[i - 2];
注意我们这里不关心dp[0]是多少。因为按照定义,应该有dp[0] = 0,但是又应该要dp[0] = 1才能递归正确。实际上这道题n是大于等于1的,所以dp[0]也正好没有意义。我们直接初始化dp[1]dp[2],然后从dp[3]开始计算即可。

class Solution {
  public:
    int climbStairs(int n) {
        if (n <= 1) {
            return n;
        }
        vector<int> dp(n + 1);
        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];
    }
};

[118] Pascal's Triangle

难度:Easy
语言:C++

题目描述
就按照杨辉三角形(英文这边叫Pascal’s Triangle)定义一行一行算即可,类似动态规划已经把状态转移方程告诉你,直接填表就行了,无思考难度。
我们先把每一行的最左右两边填上1(result[i][0] = result[i][i] = 1;),然后再依次填中间的,省去了边界特殊情况判断的麻烦。

class Solution {
  public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result(numRows);
        for (int i = 0; i < numRows; ++i) {
            result[i].resize(i + 1);
            result[i][0] = result[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
            }
        }
        return result;
    }
};

[198] House Robber

难度:Medium
语言:C++

题目描述
比较基础的动态规划,代码照着写就完事。

  • 状态转移方程dp[i]=max(dp[i2]+nums[i],dp[i1])dp[i] = \max (dp[i-2] + nums[i], dp[i -1])
  • 初始状态dp[0]=nums[0],dp[1]=max(nums[0],nums[1])dp[0] = nums[0], dp[1] = \max (nums[0], nums[1])
class Solution {
  public:
    int rob(vector<int> &nums) {
        int n = nums.size();
        if (n == 1) {
            return nums[0];
        }
        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < n; ++i) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[n - 1];
    }
};

[279] Perfect Squares

难度:Medium
语言:C++

题目描述

  • 状态转移方程dp[i]=min(dp[ij2]+1,dp[i]),jj<=idp[i] = \min (dp[i - j^2] + 1, dp[i]), \forall j * j <= i
  • 初始状态dp[0]=0dp[0] = 0

代码照着写就完事。

class Solution {
  public:
    int numSquares(int n) {
        vector<int> dp(n + 1, __INT_MAX__);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j * j <= i; ++j) {
                dp[i] = min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
};

[322] Coin Change

难度:Medium
语言:C++

题目描述

  • 状态转移方程dp[i]=min(dp[ic]+1,dp[i]),c<=idp[i] = \min (dp[i - c] + 1, dp[i]), \forall c <= i
  • 初始状态dp[0]=0dp[0] = 0

就上题的状态转移方程稍微改一丢丢,一类题,没什么区别。
需要注意的是若无解需要返回-1,所以需要额外注意一下dp值为__INT_MAX__的情况。

class Solution {
  public:
    int coinChange(vector<int> &coins, int amount) {
        vector<int> dp(amount + 1, __INT_MAX__);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int c : coins) {
                if (c <= i && dp[i - c] != __INT_MAX__) {
                    dp[i] = min(dp[i - c] + 1, dp[i]);
                }
            }
        }
        return dp[amount] == __INT_MAX__ ? -1 : dp[amount];
    }
};