leetcode算法题hot100（1）

使用C++完成leetcode算法题hot100（有选择地记录），并记录算法思路和心路历程。

🔥图论

200. 岛屿数量

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == '0')    return;
        grid[i][j] = '0';    // 消除看过的岛屿
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
};

• 主函数遍历每个点，发现有地面后，开始对该岛屿进行深度优先搜索。
• 搜索方式是递归，遇到水该点就不进行搜索，遇到地面则往四个方向搜索，并将该点其标记为0。这样一个岛屿就会被逐渐消除。主函数计数+1。
• 搜索完该岛屿后回到主函数，就会找下一个岛屿继续搜。

994. 腐烂的橘子

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> que;
        int count = 0;
        for (int i = 0; i < m; i++) {       // 数好橘子，把坏橘子推入队列
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
                else if (grid[i][j] == 2) {
                    que.push({i, j});
                }
            }
        }
        int times = 0;
        while (count > 0 && !que.empty()) {     // 模拟腐坏过程（广度优先）
            times++;
            int len = que.size();
            for (int i = 0; i < len; i++) {
                pair<int, int> pos = que.front();
                int row = pos.first, col = pos.second;
                que.pop();
                if (row + 1 < m && grid[row + 1][col] == 1) {
                    grid[row + 1][col] = 2;
                    que.push({row + 1, col});
                    count--;
                }
                if (row - 1 >= 0 && grid[row - 1][col] == 1) {
                    grid[row - 1][col] = 2;
                    que.push({row - 1, col});
                    count--;
                }
                if (col + 1 < n && grid[row][col + 1] == 1) {
                    grid[row][col + 1] = 2;
                    que.push({row, col + 1});
                    count--;
                }
                if (col - 1 >= 0 && grid[row][col - 1] == 1) {
                    grid[row][col - 1] = 2;
                    que.push({row, col - 1});
                    count--;
                }
            }
        }
        if (count > 0)  return -1;
        return times;
    }
};

• 肝代码题，思路不复杂，就是先统计好的橘子，把坏的橘子的坐标推入队列。
• 然后开始广度优先搜索（腐坏的过程本质就是广度优先），每个时间步当中，对每个坏橘子，让其四个方向的橘子变烂，减少好橘子计数。该烂橘子推出队列（因为下个时间它周围肯定只有坏橘子，没有推演的必要了）。
• 最后好橘子计数为0，说明完成全过程。

207. 课程表

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prereq) {
        vector<int> inDegree(numCourses);
        unordered_map<int, vector<int>> map;
        for (int i = 0; i < prereq.size(); ++i) {
            inDegree[prereq[i][0]]++;           // 后修课的先修课程数+1
            map[prereq[i][1]].push_back(prereq[i][0]); // 先修课的后继课程记录下来
        }
        queue<int> que;         // 当前能修的课程
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0)   que.push(i);     // 没有先修要求的课先来
        }
        int count = 0;          // 已完成的课程
        while (!que.empty()) {
            int cur = que.front();
            que.pop();
            count++;
            for (int i = 0; i < map[cur].size(); i++) { // 遍历该课的后继课
                if (inDegree[map[cur][i]] > 0) {
                    inDegree[map[cur][i]]--;
                    if (inDegree[map[cur][i]] == 0)
                        que.push(map[cur][i]);        // 有一门课先修都完成就可以修了
                }
            }
        }
        if (count == numCourses) return true;
        return false;
    }
};

• 考验写代码逻辑性。思路还是比较清晰的。
• 第一个for循环，记录所有课的先修课个数，用哈希映射记录先修课都有哪些后继课。
• 第二个for循环，把所有先修课都为0的课推入队列，因为这些课可以先修课都完成，可以修。
• while循环，不断把队列中的课程推出（模拟上完了课程），那么就可以查找需要该先修课的后继课，并减少它们当前需要的先修课个数，如果某个后继课已经没有先修课要上了，就可以推入队列。
• 最后队列空了，如果还有课就说明不能完成，反之则可以完成。

208. 实现 Trie (前缀树)

class Trie {
private:
    bool isEnd;
    Trie* next[26];
public:
    Trie() {        // 初始化
        isEnd = false;
        memset(next, 0, sizeof(next));  // 对Trie内存区域进行初始化0
    }
    
    void insert(string word) {
        Trie* node = this;
        for (char c: word) {
            if (!node->next[c - 'a'])       // 没有该孩子节点就创建一个
                node->next[c - 'a'] = new Trie();
            node = node->next[c - 'a'];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        Trie* node = this;
        for (char c: word) {
            node = node->next[c - 'a'];
            if (node == NULL)   return false;
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie* node = this;
        for (char c: prefix) {
            node = node->next[c - 'a'];
            if (node == NULL)   return false;
        }
        return true;
    }
};

• 初见比较难做出来，用26叉树实现。
• insert函数就是对单词的每个字母都构建一个节点，同一层已有该字母就不需要创建可以直接连接（所以实际上属于图而不是树）。但是不同层（比如app和dad的a是不同位置的）还是要有不同的节点。最后以isEnd标记该单词结束。
• search函数就是从根节点开始，遍历单词的每个字母，如果某个字母不存在就返回false。starstWith函数同理，只不过不需要存在完整的单词，也就是不需要判断isEnd。

🔥堆栈

20. 有效的括号

class Solution {
public:
    bool isValid(string s) {
        stack<int> stk;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') stk.push(')');
            else if (s[i] == '{') stk.push('}');
            else if (s[i] == '[') stk.push(']');
            else if (stk.empty() || stk.top() != s[i]) return false;  // 不匹配
            else    stk.pop();
        }
        return stk.empty();
    }
};

• 用栈匹配，遇到左括号时推入的是左括号匹配的右括号，那样当遇到右括号时可以直接匹配。

739. 每日温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& t) {
        stack<int> st;
        vector<int> ans(t.size());
        for (int i = 0; i < t.size(); ++i) {
            while (!st.empty() && t[st.top()] < t[i]) {
                ans[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }
};

• 栈内的元素表示还没找到更高温度的日期，所以当找到更高温度时，当前日期减去栈顶日期就是天数。

347. 前 K 个高频元素

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map <int, int> map;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            map[nums[i]]++;
        }
        priority_queue<pair<int, int>> priQue;
        for (auto& pair : map) {
            priQue.emplace(pair.second, pair.first);
        }
        vector<int> result;
        for (int i = 0; i < k; i++) {
            result.push_back(priQue.top().second);
            priQue.pop();
        }
        return result;
    }
};

• 第一个循环用哈希映射计数。
• 第二个循环用优先队列（大根堆）存放哈希映射当中的pair，把频率放在第一个可以自动按它排序。
• 第三个循环，队列前k个就是目标数，取出来即可（这里的priQue.top().second已经是上一个循环的pair.first了，不要混淆。

295. 数据流的中位数

class MedianFinder {
public:
    priority_queue<int, vector<int>, greater<int>> queL;    // greater是从小到大（小在前）
    priority_queue<int, vector<int>, less<int>> queS;
    MedianFinder() {}
    
    void addNum(int num) {
        if (queL.empty() || num >= queL.top()) {
            queL.push(num);
            if (queL.size() - queS.size() > 1) {
                queS.push(queL.top());
                queL.pop();
            }
        }
        else {
            queS.push(num);
            if (queS.size() - queL.size() > 0) {
                queL.push(queS.top());
                queS.pop();
            }
        }
    }
    
    double findMedian() {
        if (queL.size() > queS.size())  return queL.top();
        return (queL.top() + queS.top()) / 2.0;
    } 
};

• 用大根堆存小的一半值，小根堆存大的一半值。也就是两个队列的队首元素就是最中间的两个元素。这里设置queL可以多一个元素，这样两个队列大小一致时，就取两个队首均值，若queL多一个元素，则取queL的队首。
• 注意：greater<int>是小的在前，less<int>是大的在前。

🔥二分查找

35. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] < target) {
                left = mid + 1;
            }
            else if (nums[mid] > target) {
                right = mid - 1;
            }
            else    return mid;
        }
        return left;
    }
};

• 二分法，没啥好说的。

74. 搜索二维矩阵

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int up = -1, down = m - 1, left = 0, right = n - 1, mid = 0;
        while (up < down) {
            mid = (down - up + 1) / 2 + up;
            if (target == matrix[mid][0]) return true;
            if (target < matrix[mid][0]) down = mid - 1;
            else up = mid;
        }
        if (up < 0) return false;
        int row = mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (target == matrix[row][mid])  return true;
            if (target < matrix[row][mid]) right = mid - 1;
            else left = mid + 1;
        }
        return false;
    }
};

• 先二分法查找行，再二分法查找列即可。
• 注意两次查找的边界条件不一样。搜索行时，当发现行首小于目标值时，下一次up应该从该行开始而非下一行。

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, ans;
        if (nums.size() == 0) return {-1, -1};
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
                ans = mid;
            }else left = mid + 1;
        }
        if (nums[ans] != target) return {-1, -1};
        vector<int> result;
        result.push_back(ans);
        left = ans;
        right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
                ans = right;
            }
            else left = mid + 1;
        }
        result.push_back(right);
        return result;
    }
};

• 两次二分查找，分别找目标值区间的左端点和右端点。

33. 搜索旋转排序数组

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 1, n = nums.size(), right = n - 1;
        int cut = 0;        // 断点（不升序）
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[0])    left = mid + 1;
            else {
                right = mid - 1;
                cut = mid;
            }
        }
        left = cut;
        right = cut + n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid % n] == target)    return mid % n;
            if (nums[mid % n] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
};

• 先二分法寻找断点，也就是最小值的位置。
• 然后用二分法寻找目标值，right = cut + n - 1是假设把前半段接回来变成升序数组，这样方便求mid，但实际上数组没有接回来，所以mid % n就是实际的下标。

🔥回溯

46. 全排列

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void trackback(vector<int>& nums, vector<bool>& used) {
        if (nums.size() == path.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i])    continue;
            used[i] = true;         // 用过标记
            path.push_back(nums[i]);
            trackback(nums, used);      // 找下一个
            path.pop_back(); // 回溯
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        trackback(nums, used);
        return result;
    }
};

• 回溯，每一层只填某个位置的值（每个数都填一次），并把填上的标记为用过，传给下一个位置。回溯时要复原path和used给下一次循环使用。

78. 子集

class Solution {
public:
    vector<vector<int>> result;     // 所有子集
    vector<int> path;       // 单个子集
    void trackback(vector<int>& nums, int index) {
        result.push_back(path);     // 没有终止条件，是个集合不重复都行
        for (int i = index; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            trackback(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        trackback(nums, 0);
        return result;
    }
};

• 子集不需要终止条件，每一步都会生成新的不重复的子集。

17. 电话号码的字母组合

class Solution {
public:
    const string map[10] = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz",
    };
    vector<string> result;
    string str;
    void trackback(string digits, int index) {
        if (digits.size() == str.size()) {
            result.push_back(str);
            return;
        }
        string letters = map[int(digits[index] - '0')];
        for (int i = 0; i < letters.size(); i++) {
            str.push_back(letters[i]);
            trackback(digits, index + 1);
            str.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if (!digits.size()) return result;
        trackback(digits, 0);
        return result;
    }
};

• 用数组记录号码和字母的映射关系，过程和排列一样，就是每层递归填一个位置，只不过不同按钮字母不同没有重复问题。

39. 组合总和

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void trackback(vector<int>& candidates, int index, int sum, int target) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = index; i < candidates.size() && sum + candidates[i] <= target; i++) {
            path.push_back(candidates[i]);
            trackback(candidates, i, sum + candidates[i], target);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        trackback(candidates, 0, 0, target);
        return result;
    }
};

• 首先要排序数组，从小到大填，依然是每层递归只填一个位置（尝试所有数）。
• 只不过有2个中止条件：一是当前和到达目标值；二是如果下一个要填的数加上去大于目标值，就不填，说明这个解不可能了。

22. 括号生成

class Solution {
public:
    vector<string> result;
    string str;
    void trackback(int n, int left, int right) {
        if (str.size() == n * 2) {
            result.push_back(str);
            return;    
        }
        if (left < n) {
            str.push_back('(');
            trackback(n, left + 1, right);
            str.pop_back();
        }
        if (right < left) {
            str.push_back(')');
            trackback(n, left, right + 1);
            str.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        trackback(n, 0, 0);
        return result;
    }
};

• left和right是记录当前已有的左右括号数，当左括号少于n就可以填入，右括号少于左括号也可以填入。这里每层就不一定只填一个括号了。

79. 单词搜索

class Solution {
public:
    const vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};  // 四个方向
    bool check(vector<vector<char>>& board, string word, int i, int j, vector<vector<bool>>& visited, int curIndex) {
        if (board[i][j] != word[curIndex])    return false;
        else if (curIndex == word.size() - 1)   return true;
        // 接下来对符合的字母进行四个方向的查找
        visited[i][j] = true;
        bool result = false;            // 四个方向是否有对应值
        for (const auto& dir: directions) {      // 四个方向
            int newi = i + dir.first, newj = j + dir.second;
            // 坐标没有越界
            if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) {
                if (!visited[newi][newj]) {     // 不能遍历重复的格子
                    bool res = check(board, word, newi, newj, visited, curIndex + 1); //递归
                    if (res) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;      // 回溯
        return result;

    }
    bool exist(vector<vector<char>>& board, string word) {
        int h = board.size(), w = board[0].size();
        vector<vector<bool>> visited(h, vector<bool>(w));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (check(board, word, i, j, visited, 0))
                    return true;
            }
        }
        return false;
    }
};

• 主函数exist当中遍历每个格子作为词的首字母。递归当中，每一层都判断该点是否符合，若符合就向四个方向继续探索一格。
• 用visited数组记录已经访问过的格子，避免重复访问，回溯时需要复原。

131. 分割回文串

class Solution {
public:
    vector<vector<string>> result;
    vector<string> path;
    void trackback(string s, int index) {
        if (index >= s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = index; i < s.size(); i++) {
            if (isValid(s, index, i)) {
                string sub = s.substr(index, i - index + 1);
                path.push_back(sub);        // 找到下一个回文子串
                trackback(s, i + 1);
                path.pop_back();         // 回溯
            }
        }
    }
    bool isValid(string s, int start, int end) {        // 判断是不是回文串
        for (int i = start, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) return false;
        }
        return true;
    }
    vector<vector<string>> partition(string s) {
        trackback(s, 0);
        return result;
    }
};

• 回溯，其实还是类似排列，只不过是判断每个位置是否要割。
• 如果切割后左边产生的新子串不是回文的，就不继续割（错解，终止情况1），反之则继续。终止情况2是每个位置都判断过了（index大小和s的长度一致），说明这次解是正确的。

51. N 皇后

class Solution {
public:
    vector<vector<string>> result;
    void trackback(int n, int row, vector<string>& board) {
        if (row == n) {
            result.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, board, n)) {
                board[row][col] = 'Q';        // 可以放置皇后
                trackback(n, row + 1, board);
                board[row][col] = '.';        // 回溯（还原棋盘）
            }
        }
    }
    bool isValid(int row, int col, vector<string>& board, int n) {
        // 同一列是否有别的皇后
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // 正对角（右下方还没放，不需要遍历）
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q')   return false;
        }
        // 反对角（左下方还没放，不需要遍历）
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q')   return false;
        }
        return true;
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));     // 棋盘初始化（n*n个'.'）
        trackback(n, 0, board);
        return result;
    }
};

• 每一层递归负责对某一行的所有格子都尝试放一个皇后，用isValid判断是否符合条件（只要判断这个位置的同一列、两个对角线上是不是有已经放过的皇后），符合就放置。
• 终止条件：若所有行都放完（row超出n），说明是正解。

🔥贪心算法

121. 买卖股票的最佳时机

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        int minP = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            minP = min(minP, prices[i]);
            result = max(prices[i] - minP, result);
        }
        return result;
    }
};

• 比较简单，就是找到最大的差值（升序）。

55. 跳跃游戏

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if (nums.size() == 1) return true;
        for (int i = 0; i <= cover; i++) {
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1)   return true;
        }
        return false;
    }
};

• 这里只要判断理论上能不能到终点，所以只要逐步判断最远覆盖范围是否能到达终点即可。

45. 跳跃游戏 II

class Solution {
public:
    int jump(vector<int>& nums) {
        int cover = 0;
        int nextCover = 0;
        int ans = 0;
        for (int i = 0; i < nums.size() - 1; ++i) {
            nextCover = max(nums[i] + i, nextCover);
            if (i == cover) {
                ans++;
                cover = nextCover;
            }
        }
        return ans;
    }
};

• 需要维护两个范围，分别是当前步和下一步能走到的最远距离，到达这个最远位置cover后，就必须再走一步了（ans+1），最远距离就更新为下一个最远距离。
• 宏观来看，有多少段cover就要走多少步（每一段里面有且只有一步）。

763. 划分字母区间

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26];
        int n = s.size();
        vector<int> result;
        for (int i = 0; i < n; i++) {
            last[s[i] - 'a'] = i;
        }
        int left = 0, right = 0;
        for (int i = 0; i < n; i++) {
            right = max(right, last[s[i] - 'a']);   // 右端点随着新的字母出现而更新
            if (i == right) {     // 该区间到底
                result.push_back(right - left + 1);
                left = right + 1;
            }
        }
        return result;
    }
};

• 先遍历一次字符串，记录所有字母最后出现的位置。再遍历一次，维护区间右边界，该右边界是目前区间当中字母最后出现的位置。当遍历到右边界说明该边界到头了，区间里面完整地包含了若干个字母。可以导出该区间长度。

🔥动态规划

70. 爬楼梯

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n == 1 ? 1 : 2;
        vector<int> dp(n);
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; 
        }
        return dp[n - 1];
    }
};

• dp是到第i层台阶的走法，走到第i层要么来自于i-1层，要么来自于i-2层，所以每一层的走法是前两层走法之和。
• 对只有1、2个台阶的情况要专门处理。

198. 打家劫舍

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) {
            return n == 1 ? nums[0] : max(nums[0], nums[1]);
        }
        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = nums[0] + nums[2];
        for (int i = 3; i < n; i++) {
            dp[i] = max(dp[i - 2], dp[i - 3]) + nums[i];
        }
        return max(dp[n - 2], dp[n - 1]);
    }
};

• dp是抢到第i个房子时的总收益，dp[i]来源于抢第i-2或第i-3个房子的收益加上该房子的收益（也就是如果抢i，i-2和i-3一定会抢一个）。
• 最后两个房子一定会抢一个。

118. 杨辉三角

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

• 就按要求每行的第i个元素来源于上一行第i-1个和第i个元素之和，每行两边都是1。

279. 完全平方数

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

• 完全背包问题，容量n，物品就是完全平方数（开根号后遍历），dp[i]是装到容量i时需要的最少物品。
• 对于每个容量，其dp来自于dp[不放某个物品的容量数]的最小值 + 1，内层循环遍历了所有物品找到这个最小值来维护minN。

322. 零钱兑换

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

• dp是到达容量j所需要的最少硬币数。对于每个硬币，到达容量j的最少硬币数来源于到达容量j-coin的所需最少硬币数加1，也就是dp[j - coin] + 1，维护最小的dp[j]即可。
• if (dp[j - coins[i]] != INT_MAX)是指这个前置数额压根凑不到的时候j数额也不可能凑到，所以跳过。举个例子，对于硬币2，凑到5元，发现之前3元压根凑不到，那么就不能指望通过2+3凑到5元了。

139. 单词拆分

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 0; j < i; j++) {
                string sub = s.substr(j, i - j);
                if (wordSet.find(sub) != wordSet.end() && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

• 原理层面：对于每个子串（外层循环），在每个点分割该子串（内层循环）得到两个小子串，判断左子串是否可分割且右子串在词典中。
• 代码层面：dp[i]表示前i个字符是否可以拆分，那么wordSet.find(sub) != wordSet.end() && dp[j]，就是前j个字符可以拆分，并且j到i的子串在wordSet中，那么这i个字符构成的子串就可以拆分。

300. 最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(), 1);
        int result = 0;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[j] + 1, dp[i]);
                }
            }
            result = max(result, dp[i]);
        }
        return result;
    }
};

• 和上一题差不多，也是对每个子串的所有元素再遍历分析的嵌套双循环结构。对于每个数nums[i]其前置数可能来自前面任何一个比它小的数nums[j]，维护它们当中的最大的dp[j]+1即可，然后再维护全局的最大值result。

152. 乘积最大子数组

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        long maxF = nums[0], minF = nums[0], ans = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            long mx = maxF, mn = minF;
            maxF = max({mx * nums[i], mn * nums[i], (long)nums[i]});
            minF = min({mx * nums[i], mn * nums[i], (long)nums[i]});
            ans = max(maxF, ans);
        }
        return ans;
    }
};

• 由于存在负数，所以每一次的最大积是来自前面最大的正数积或前面最小的负数积或当前值本身（因为可能前面的积没有正数，这个数是正数那就是最大了），三者取最大即可。而ans来自于最终的最大正数。

416. 分割等和子集

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
        }
        if (sum % 2)    return false;   // 和为奇数，无法等分
        int target = sum / 2;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if (dp[target] == target)   return true;
        return false;
    }
};

• 分成两个子集，所以只需要找到一个子集的和为一半1的数组和即可。
• 所以先计算总和，排除奇数总和（不可能平分），然后再当01背包问题解决。遍历每一个物品，对于每一个容量，其dp值来源于dp[j - nums[i]] + nums[i]，即容量j-nums[i]的容量的dp值加上当前物品nums[i]，然后维护最大值即可。
• 注意：内层循环倒序遍历，因为如果正序，那么同一个物品可能会被放入多次（也就是dp[j - nums[i]]可能就是放过num[i]的情况了），而01背包问题要求物品不能重复放入，所以倒序遍历。

32. 最长有效括号

class Solution {
public:
    int longestValidParentheses(string s) {
        int result = 0;
        stack<int> stk;
        stk.push(-1);
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                stk.push(i);
            }
            else {
                stk.pop();
                if (stk.empty())    stk.push(i);
                else result = max(result, i - stk.top());
            }
        }
        return result;
    }
};

• 这题用动态规划比较麻烦，这里用栈解决，把左括号索引压入栈，遇到右括号时栈顶的左括号就是和它匹配的，出栈。
• 出栈后，此时新的栈顶元素就是有效区间的左端点-1，计算当前索引和栈顶索引的距离就是区间长度了，维护其最大值。

🔥多维动态规划

62. 不同路径

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

• 每个格子都来自于上一格或者左一格，把两者都路径加起来即可。
• 初始化矩阵，第一行和第一列都是1，因为都只有1种路径。

64. 最小路径和

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = grid[0][0];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j== 0) continue;
                if (i == 0) dp[i][j] = dp[i][j - 1] + grid[i][j];
                else if (j == 0) dp[i][j] = dp[i - 1][j] + grid[i][j];
                else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};

• 和上一题差不多，每个格子的累计和来自于左一格或者上一格的更小者，再加上本格值即可。
• 对原点初始化，推演时，左边和上边只能来自于一个方向要用if区分。

5. 最长回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        int len = 0;
        string res;
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1 || dp[i + 1][j - 1]) {
                        if (len < j - i + 1) {
                            len = j - i + 1;        // 维护最长长度
                            res = s.substr(i, len);
                        }
                        dp[i][j] = true;
                    }
                }
            }
        }
        return res;
    }
};

• dp[i][j]是指从i~j的这段子串是否是回文的，双层循环从两个方向遍历了所有子串，每个子串dp都来自于dp[i+1][j-1]是回文且s[i] == s[j]。维护最长长度，并更新最长回文子串。

1143. 最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

• dp[i][j]表示text1[0...i-1]和text2[0...j-1]的最长公共子序列长度，如果text1[i-1] == text2[j-1]，子序列多了一个成员，就可以直接在dp[i-1][j-1]基础上+1了；否则dp[i][j]就来自于dp[i][j-1]和dp[i-1][j]的更大者。
• 初始化时+1代表了空串，即空串和任何串的最长公共子序列长度都是0。

72. 编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        for (int i = 1; i <= word1.size(); i++)  dp[i][0] = i;
        for (int j = 1; j <= word2.size(); j++)  dp[0][j] = j;
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                if (word1[i - 1] == word2[j - 1])   dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

• 思路和上一题类似，同步遍历两个串，考虑空串到，dp初始化长度也要+1。
• dp[i][j]代表word1[0...i-1]到word2[0...j-1]的编辑距离，如果word1[i-1] == word2[j-1]，则不需要做任何操作，dp[i][j]就等于dp[i-1][j-1]；否则，就需要采取三种操作，分别是删除、插入、替换，dp[i][j]就是三个操作执行前的三个dp的最小者加1。