DP入门（存储之前状态以简化）
思路：
方法：动态规划
状态：
子状态：前1 ， 2 ， 3 ， ...,n 个字符能否根据词典中的词被成功分词
F(i): 前 i 个字符能否根据词典中的词被成功分词
状态递推：
F(i): true{j <i && F(j) && substr[j,i-j]能在词典中找到 } OR false
在j 小于 i 中，只要能找到一个 F(j) 为 true ，并且从 j+1 到 i 之间的字符能在词典
中找到，则F(i) 为 true
初始值：
对于初始值无法确定的，可以引入一个不代表实际意义的空状态，作为状态的起始
空状态的值需要保证状态递推可以正确且顺利的进行，到底取什么值可以通过简单
的例子进行验证
F(0) = true
返回结果： F(n)
例如题目样例：
当i==3时 有F[0]==true&&可找到[0,3]中有now，所以canbreak[3]==true;
当i==7时 有F[3]==true&&可找到[3,7]有code，所以canbreak[7]==true;
总结：利用F[i]存之前的状态是否可分割，然后搜索后面有无字符，两者都为true则这个整体可分割
class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { if(s.empty()) return false; if(dict.empty()) return false; vector<bool> canbreak(s.size()+1,false); canbreak[0]=true; for(int i=1;i<=s.size();i++) for(int j=i-1;j>=0;j--){ if(canbreak[j]&&dict.find(s.substr(j,i-j))!=dict.end()){ // F(i): true{j <i && F(j) && substr[j+1,i]能在词典中找到} OR false canbreak[i]=true; break; } } return canbreak[s.size()]; } };
DP解决最短路问题
状态：
子状态：从(0,0) 到 (1,0),(1,1),(2,0),...(n,n) 的最短路径和
F(i,j): 从 (0,0) 到 (i,j) 的最短路径和
状态递推：
F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
初始值：
F(0,0) = triangle[0][0]
返回结果：
min(F(n-1, i))
方法一：递推法
利用dp算出所有路径，再找最短值
class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { if(triangle.empty()) return 0; vector<vector<int>> minsum(triangle); int line=triangle.size(); for(int i=1;i<line;i++){ for(int j=0;j<=i;j++){ //处理左右边界 if(j==0) minsum[i][j]=minsum[i-1][j]+triangle[i][j]; else if(j==i) minsum[i][j]=minsum[i-1][j-1]+triangle[i][j]; else{//核心操作 minsum[i][j]=min(minsum[i-1][j],minsum[i-1][j-1])+triangle[i][j]; } } } int res=minsum[line-1][0];//找到最后一行的最短步数 for(int i=1;i<line;i++) res=min(res,minsum[line-1][i]); return res; } };
方法二：逆推法
状态：
子状态：
从(n,n),(n,n-1),...(1,0),(1,1),(0,0) 到最后一行的最短路径和
F(i,j): 从 (i,j)到最后一行的最短路径和
状态递推：
F(i,j) = min( F(i+1, j), F(i+1, j+1)) + triangle[i][j]
初始值：
F(n-1,0) = triangle[n-1][0], F(n-1,1) = triangle[n-1][1],..., F(n-1,n-1) = triangle[n-1] [n-1]
返回结果：
F(0, 0)
class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { if(triangle.empty()) return 0; vector<vector<int>> minsum(triangle); int line=triangle.size(); // 从倒数第二行开始 for(int i=line-2;i>=0;i--) { for(int j=0;j<=i;j++){ minsum[i][j]=min(minsum[i+1][j],minsum[i+1][j+1])+triangle[i][j]; } } return minsum[0][0]; } };
