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

文章目录

• • • 1. 单词拆分
    • 2. 最长递增子序列

      1. 单词拆分

      题目链接

      ---

      • 🍎 解题思路：

      • ---

        class Solution { bool dp[310] = {false};
        public:
            bool wordBreak(string s, vector& wordDict) { unordered_set 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. 最长递增子序列

        题目链接🔗