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[i-2] + nums[i], dp[i -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[i - j^2] + 1, dp[i]), \forall j * j <= i$
初始状态 $dp[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[i - c] + 1, dp[i]), \forall c <= i$
初始状态 $dp[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];
    }
};

AllenY's blog