【力扣刷题 动态规划】LeetCode 139 单词拆分、LeetCode 300 最长递增子序列 ✌

1. 单词拆分

题目链接

---

• 🍎 解题思路：
• 

---

class Solution {

    bool dp[310] = {false};

public:
    bool wordBreak(string s, vector<string>& wordDict) {

        unordered_set<string> myset;
        
        for(auto& str : wordDict)
            myset.insert(str);

        s = " " + s;

        // dp[i] 表示 [1, i]的区间内能否被单词拼接而成
        dp[0] = true;

        int n = s.size();

        for (int i = 1; i <= n; i ++)    
        {                                   
            for (int j = 1; j <= i; j ++)       
            {
                string str = s.substr(j, i - j + 1);

                if (dp[j - 1] == true && myset.count(str) > 0)
                {
                    dp[i] = true;
                }
            }       
        }
        return dp[n];
    }
};

---

2. 最长递增子序列

题目链接🔗