题目地址：

简单的动态规划问题，采用自顶向下的备忘录方法，代码如下：

1 class Solution { 2 public: 3     bool dictContain(unordered_set
     
       &dict, string s) 4     { 5         unordered_set
      
       ::iterator ite = dict.find(s); 6         if(ite != dict.end()) 7             return true; 8         else return false; 9     }10 11     bool wordBreak(string s, unordered_set
       
         &dict)12     {13         // Note: The Solution object is instantiated only once and is reused by each test case.14         if(dict.empty())15             return false;16         const int len = s.size();17         bool canBreak[len]; //canBreak[i] = true 表示s[0~i]是否能break18         memset(canBreak, 0, sizeof(bool)*len);19         for(int i = 1; i <= len; i++)20         {21             if(canBreak[i-1] == false && dictContain(dict, s.substr(0, i)))22                 canBreak[i-1] = true;23 24             if(canBreak[i-1] == true)25             {26                 if(i == len)return true;27                 for(int j = 1; j <= len - i; j++)28                 {29                     if(canBreak[j+i-1] == false && dictContain(dict,s.substr(i, j)))30                         canBreak[j+i-1] = true;31 32                     if(j == len - i && canBreak[j+i-1] == true)return true;33 34                 }35             }36 37         }38 39         return false;40     }41 42 43 };
       
      
     

注意：在本机调试时，编译器要开启c++11支持，因为#include<unordered_set>是c++11的标准

---

相关参考资料

微信公共账号“待字闺中”也有关于此题的讨论：请点击 或

【版权声明】转载请注明出处：