动态规划

509. 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你 n ，请计算 F(n) 。

class Solution {
public:
    int fib(int n) {
      int a[3] = {0, 1, 1};
      if (n <= 2) {
        return a[n];
      }
      for (int i = 3; i <= n; i++) {
        a[i % 3] = a[(i - 1) % 3] + a[(i - 2) % 3];
      }
      return a[n % 3];
    }
};

70. 爬楼梯

力扣题目链接(opens new window)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

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

746. 使用最小花费爬楼梯

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if (cost.size() == 1) {
            return cost[0];
        }
        if (cost.size() == 2) {
            return min(cost[0], cost[1]);
        }
        vector<int> dp(cost.size() + 1);
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i < dp.size(); i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return *dp.rbegin();
    }
};

62. 不同路径

力扣题目链接(opens new window)

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

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

63. 不同路径 II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        vector<vector<int>> dp(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 1));
        for (int i = 1; i < dp.size(); i++) {
            dp[i][0] = obstacleGrid[i][0] ? 0 : dp[i - 1][0];
        }
        for (int i = 1; i < dp[0].size(); i++) {
            dp[0][i] = obstacleGrid[0][i] ? 0 : dp[0][i - 1];
        }
        for (int i = 1; i < dp.size(); i++) {
            for (int j = 1; j < dp[0].size(); j++) {
                dp[i][j] = obstacleGrid[i][j] ? 0 : dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[dp.size() - 1][dp[0].size() - 1];
    }
};

343. 整数拆分

力扣题目链接(opens new window)

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

class Solution {
public:
    int integerBreak(int n) {
        int ans = 1;
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        if (n == 4) {
            return 4;
        }
        while (n > 4) {
            n -= 3;
            ans *= 3;
        }
        ans *= n;
        return ans;
    }
};

416. 分割等和子集

力扣题目链接(opens new window)

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

0-1 背包问题，但这个背包的定义好难想到

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0) {
            return false;
        }
        sum /= 2;
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = sum; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        return dp[sum] == sum;
    }
};

1049. 最后一块石头的重量 II

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int target = sum / 2;
        vector dp(15001, 0);
        for (int i = 0; i < stones.size(); i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2 * dp[target];
    }
};

494. 目标和

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // x - (sum - x) = target
        // x = (sum + target) / 2;
        if ((sum + target) % 2 != 0) {
            return 0;
        }
        if (abs(target) > sum) {
            return 0;
        }
        int bagSize = (sum + target) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};

474. 一和零

纪念一下第一次自己做出来的 0-1 背包问题

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        // dp[m][n] means the max count of items
        int dp[101][101] = {0};
        for (int i = 0; i < strs.size(); i++) {
            string& str = strs[i];
            int count0 = 0, count1 = 0;
            for (const auto c : str) {
                if (c == '0') {
                    count0++;
                } else {
                    count1++;
                }
            }
            for (int j = m; j >= count0; j--) {
                for (int k = n; k >= count1; k--) {
                    dp[j][k] = max(dp[j-count0][k-count1] + 1, dp[j][k]);
                }
            }
            // dp[m][n] = max(dp[m-count0][n-count1] + 1, dp[m][n])
        }
        return dp[m][n];
    }
};

518. 零钱兑换 II

力扣题目链接(opens new window)

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

完全背包问题

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

377. 组合总和 Ⅳ

力扣题目链接

关于这里的 dp[j] < INT_MAX - dp[j - nums[i]]，题目保证「题目数据保证答案符合 32 位整数范围」，但并没有保证中间数据不超过此范围。

溢出的状态解压根没转移到最终的解，也就是最终解跟溢出的中间结果没有关系，感觉上是测试样例有点特殊。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
      int dp[1001] = {0};
      dp[0] = 1;
      for (int j = 1; j <= target; j++) {
        for (int i = 0; i < nums.size(); i++) {
          if (j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]]) {
            dp[j] += dp[j - nums[i]];
          }
        }
      }
      return dp[target];
    }
};

322. 零钱兑换

力扣题目链接(opens new window)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

要考虑的边界情况还真不少

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

279. 完全平方数

力扣题目链接(opens new window)

给定正整数 n，找到若干个完全平方数（比如 1,4, 9,16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

先用 Python 打个表（既然如此为什么不直接把答案打表呢）

def find_perfect_squares(start, end):
    perfect_squares = []
    for num in range(start, end + 1):
        perfect_squares.append(num ** 2)
    return perfect_squares

start = 1
end = 100

result = find_perfect_squares(start, end)
print("1 到 100 的完全平方数为：", result)

再用完全背包问题求解：

class Solution {
public:
    int numSquares(int n) {
        int squares[100] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364, 3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 5041, 5184, 5329, 5476, 5625, 5776, 5929, 6084, 6241, 6400, 6561, 6724, 6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025, 9216, 9409, 9604, 9801, 10000};
        int dp[10001] = {0};
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 100; j++) {
                if (squares[j] > i) {
                    break;
                } else if (squares[j] == i) {
                    dp[i] = 1;
                    break;
                } else {
                    // squares[j] < i
                    dp[i] = dp[i] == 0 ? dp[i - squares[j]] + 1 : min(dp[i - squares[j]] + 1, dp[i]);
                }
            }
        }
        return dp[n];
    }
};

139. 单词拆分

力扣题目链接(opens new window)

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

关于 C++ 的字符串操作，一直记得不太熟

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 word = s.substr(j, i - j);
          if (wordSet.find(word) != wordSet.end() && dp[j]) {
            dp[i] = true;
            break;
          }
        }
      }
      return dp[s.size()];
    }
};

198. 打家劫舍

力扣题目链接(opens new window)

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        }
        int dp[100] = {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

力扣题目链接

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

337. 打家劫舍 III

力扣题目链接

树形 DP 问题

class Solution {
public:
    pair<int, int> traversal(TreeNode* curr) {
        if (curr == nullptr) {
            return {0, 0};
        }
        auto left  = traversal(curr->left);
        auto right = traversal(curr->right);
        int steal = curr->val + left.first + right.first;
        int no_steal = max(left.first, left.second) + max(right.first, right.second); // think
        return {no_steal, steal};
    }
    int rob(TreeNode* root) {
        auto res = traversal(root);
        return max(res.first, res.second);
    }
};

121. 买卖股票的最佳时机

力扣题目链接

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

123. 买卖股票的最佳时机 III

力扣题目链接(opens new window)

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) {
            return 0;
        }
        int dp1 = -prices[0], dp2 = 0, dp3 = -prices[0], dp4 = 0;
        for (int i = 1; i < n; i++) {
            dp1 = max(dp1, - prices[i]);
            dp2 = max(dp2, dp1 + prices[i]);
            dp3 = max(dp3, dp2 - prices[i]);
            dp4 = max(dp4, dp3 + prices[i]);
        }
        return dp4;
    }
};

188. 买卖股票的最佳时机 IV

力扣题目链接(opens new window)

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() == 0) {
            return 0;
        }
        int dp[201] = {0};
        for (int i = 0; i < k; i++) {
            dp[2 * i] = -prices[0];
        }
        for (int i = 1; i < prices.size(); i++) {
            dp[0] = max(dp[0], -prices[i]);
            dp[1] = max(dp[1], dp[0] + prices[i]);
            for (int j = 1; j < k; j++) {
                dp[2 * j] = max(dp[2 * j], dp[2 * j - 1] - prices[i]);
                dp[2 * j + 1] = max(dp[2 * j + 1], dp[2 * j] + prices[i]);
            }
        }
        return dp[2 * k - 1];
    }
};

309. 买卖股票的最佳时机含冷冻期

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) {
            return 0;
        }
        vector<vector<int>> dp(n, vector<int>(4, 0));
        dp[0][0] = -prices[0];  // own
        dp[0][1] = 0;           // solded
        dp[0][2] = 0;           // sold today
        dp[0][3] = 0;           // freeze
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][3]) - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
            dp[i][2] = dp[i - 1][0] + prices[i];
            dp[i][3] = dp[i - 1][2];
        }
        return max(max(dp[n - 1][1], dp[n - 1][2]), dp[n - 1][3]);
    }
};

714. 买卖股票的最佳时机含手续费

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        if (n == 0) {
            return 0;
        }
        int buy = -prices[0], sold = 0, newBuy;
        for (int i = 1; i < n; i++) {
            newBuy = max(buy, sold - prices[i]);
            sold = max(sold, buy + prices[i] - fee);
            buy = newBuy;
        }
        return sold;
    }
};

还有一种贪心的方法，不是那么好理解

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        if (n == 0) {
            return 0;
        }
        int buy = prices[0] + fee;
        int profit = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] + fee < buy) {
                buy = prices[i] + fee;  // 买
            } else if (prices[i] > buy) {
                profit += (prices[i] - buy);
                buy = prices[i];  // 反悔
            }
        }
        return profit;
    }
};

300. 最长递增子序列

力扣题目链接

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

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

还有一种贪心+二分的方法

用 upper_bound 写了好几次都不对……关键在于找到严格小的下一个，所以应该使用 lower_bound，太费脑子啦。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = 1;
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> dp(n + 1, 0);
        dp[len] = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] > dp[len]) {
                dp[++len] = nums[i];
            } else {
                // nums[i] <= dp[len]
                int pos = lower_bound(dp.begin() + 1, dp.begin() + len + 1, nums[i]) - dp.begin();
                dp[pos] = nums[i];
            }
        }
        return len;
    }
};

时间复杂度： $O(n\log n)$
空间复杂度： $O(n)$

674. 最长连续递增序列

比昨天简单了好多……写了贪心的解法

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        int maxLen = 1, currLen = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) {
                currLen++;
            } else {
                maxLen = max(maxLen, currLen);
                currLen = 1;
            }
        }
        return max(maxLen, currLen);
    }
};

718. 最长重复子数组

还有滑动窗口解法、二分查找+哈希解法，动态规划也有滚动数组的版本，有空记得看

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        int maxLen = 0;
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                dp[i + 1][j + 1] = nums1[i] == nums2[j] ? dp[i][j] + 1 : 0;
                maxLen = max(maxLen, dp[i + 1][j + 1]);
            }
        }
        return maxLen;
    }
};

1143. 最长公共子序列

力扣题目链接(opens new window)

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

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

1035. 不相交的线

力扣题目链接

转换为 [动态规划#1143. 最长公共子序列](动态规划.md#1143. 最长公共子序列) 问题，要有敏锐的意识！

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                dp[i + 1][j + 1] = nums1[i] == nums2[j] ? dp[i][j] + 1 : max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
        return dp[len1][len2];
    }
};

392. 判断子序列

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int len_s = s.size(), len_t = t.size();
        vector<vector<int>> dp(len_t + 1, vector<int>(26, 0));
        for (int i = 0; i < 26; i++) {
            dp[len_t][i] = len_t;
        }
        for (int i = len_t - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t[i] == 'a' + j) {
                    dp[i][j] = i;
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        int start = 0;
        for (int i = 0; i < len_s; i++) {
            if (dp[start][s[i] - 'a'] == len_t) {
                return false;
            }
            start = dp[start][s[i] - 'a'] + 1;
        }
        return true;
    }
};

115. 不同的子序列

class Solution {
    const int N = 1000000007;
public:
    int numDistinct(string s, string t) {
        int len1 = s.size(), len2 = t.size();
        if (len1 < len2) {
            return 0;
        }
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (int i = 0; i < len1; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (s[i] == t[j]) {
                    dp[i + 1][j + 1] = (dp[i][j] + dp[i][j + 1]) % N;
                } else {
                    dp[i + 1][j + 1] = dp[i][j + 1];
                }
            }
        }
        return dp[len1][len2];
    }
};

583. 两个字符串的删除操作

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size(), len2 = word2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                dp[i + 1][j + 1] = word1[i] == word2[j] ? dp[i][j] + 1 : max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
        return len1 + len2 - 2 * dp[len1][len2];
    }
};

72. 编辑距离

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

647. 回文子串

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j] && (i+ 1 >= j || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    result++;
                }
            }
        }
        return result;
    }
};

516. 最长回文子序列

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

509. 斐波那契数​

70. 爬楼梯​

746. 使用最小花费爬楼梯​

62. 不同路径​

63. 不同路径 II​

343. 整数拆分​

416. 分割等和子集​

1049. 最后一块石头的重量 II​

494. 目标和​

474. 一和零​

518. 零钱兑换 II​

377. 组合总和 Ⅳ​

322. 零钱兑换​

279. 完全平方数​

139. 单词拆分​

198. 打家劫舍​

213. 打家劫舍 II​

337. 打家劫舍 III​

121. 买卖股票的最佳时机​

123. 买卖股票的最佳时机 III​

188. 买卖股票的最佳时机 IV​

309. 买卖股票的最佳时机含冷冻期​

714. 买卖股票的最佳时机含手续费​

300. 最长递增子序列​

674. 最长连续递增序列​

718. 最长重复子数组​

1143. 最长公共子序列​

1035. 不相交的线​

392. 判断子序列​

115. 不同的子序列​

583. 两个字符串的删除操作​

72. 编辑距离​

647. 回文子串​

516. 最长回文子序列​

509. 斐波那契数

70. 爬楼梯

746. 使用最小花费爬楼梯

62. 不同路径

63. 不同路径 II

343. 整数拆分

416. 分割等和子集

1049. 最后一块石头的重量 II

494. 目标和

474. 一和零

518. 零钱兑换 II

377. 组合总和 Ⅳ

322. 零钱兑换

279. 完全平方数

139. 单词拆分

198. 打家劫舍

213. 打家劫舍 II

337. 打家劫舍 III

121. 买卖股票的最佳时机

123. 买卖股票的最佳时机 III

188. 买卖股票的最佳时机 IV

309. 买卖股票的最佳时机含冷冻期

714. 买卖股票的最佳时机含手续费

300. 最长递增子序列

674. 最长连续递增序列

718. 最长重复子数组

1143. 最长公共子序列

1035. 不相交的线

392. 判断子序列

115. 不同的子序列

583. 两个字符串的删除操作

72. 编辑距离

647. 回文子串

516. 最长回文子序列