动态规划(分割词汇)

分割词汇的第四个版本代码中,不懂oneBreak[size-1]为什么等于0。
请老师解释一下,谢谢老师。

2016-10-26_230024.jpg

 

邹博 - 计算机科学博士,深谙机器学习算法原理

赞同来自: Astro门

这个是咱们《面试算法》中“图论应用”章节的内容。为了方便其他浏览者,我截一下题目本身: 可以看出,该题目的本质即“单词划分”。
1477628008923.png
  这个是算法思路,注意划横线的部分,是如何找到所有单词划分的:
1477628094292.png
  从而,根据深度优先搜索,即可得到所有解:即该问题的截图。 当然,问题中“oneBreak[size-1]为什么等于0”其实只是C/C++语言本身的原因:字符串以0做结尾。   注:该题目可以变化成“给定句子和词典,是否存在至少一种可行划分”“给定句子和词典,给出一种可行划分”“给定句子和词典,给出所有可行划分”这三个难度,所以,咱们课件中是分别阐述,从而有了不同的代码版本。

要回复问题请先登录注册