Longest Substring Without Repeating Characters

最近刚刚看了动态规划的一些内容，就顺手做了这道题目，这道题目就是动态规划的典型应用。

解题思路

假设有字符串长度为n，用b[i]表示第0个字符到第i个字符的最长子序列的长度，那么本题的结果就是求b[n]。

1. 首先，当b[n]不是重复的字符时，b[n]=b[n-1]+1，否则b[n] = b[n-1]
2. 用cache保存已经验证属于最长子序列的字符串
3. 从字符串的第一位开始循环，如果不在cache中就加入到cache中
4. 如果已经在cache中，就从上一次出现的位置截取cache，如：原cache中存放的是abcd，此时又有一个b，那么cache就截取为cd再将b加进去
5. 最后返回cache的长度就是b[n]

JavaScript代码实现

var lengthOfLongestSubstring = function(s) {
  if (s.length < 1) {
    return 0
  }
  var temp = maxLength = 1
  var cache = s[0]
  for (let i = 1, length = s.length; i < length; i++) {
    index = cache.indexOf(s[i])
    if (index < 0) {
      temp++
      cache += s[i]
    } else {
      cache = cache.slice(index + 1)
      cache += s[i]
      temp = cache.length
    }
    if (temp > maxLength) {
      maxLength = temp
    }
  }
  return maxLength
};

关于动态规划

判断一个问题能否用动态规划来解决，可以参考这篇博客的思路:

1. 最优子结构 子问题最优时母问题通过优化选择后一定最优的情况叫做“最优子结构”
2. 子问题重叠 母问题与子问题本质上是同一个问题的情况称为“子问题重叠”
3. 边界 子问题在一定时候就不再需要提出子子问题的情况叫做边界，没有边界就会出现死循环
4. 子问题独立 一个母问题在对子问题选择时，当前被选择的子问题两两互不影响的情况叫做“子问题独立”

那么拿到一个动态规划问题应该如何处理呢？这篇博客也有很好的说明：

1. 构造问题所对应的过程。
2. 思考过程的最后一个步骤，看看有哪些选择情况。
3. 找到最后一步的子问题，确保符合“子问题重叠”，把子问题中不相同的地方设置为参数。
4. 使得子问题符合“最优子结构”。
5. 找到边界，考虑边界的各种处理方式。
6. 确保满足“子问题独立”，一般而言，如果我们是在多个子问题中选择一个作为实施方案，而不会同时实施多个方案，那么子问题就是独立的。
7. 考虑如何做备忘录。
8. 分析所需时间是否满足要求。
9. 写出转移方程式。