前言

???????继续动态规划的思想，把大问题差分成小问题，再把握各个小问题之间的规律，也就是利用 p[n-1]，dp[n-2]……dp[1]，来推出 dp[n] ，这也就是dp算法->Dynamic programming。
???????越困难的问题，越不好找到两者之间的关系，但本质上还是dp问题。

1、

??把数字翻译成字符串
???????给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”

乍一看，不仅要考虑每一个数，而且还有考虑两个数放一块是否可以翻译成字符,那如何取出两个字符呢？当然是选for、while循环解决问题，然后我们会寻找规律：

数字	翻译方法
1	1
12	12->(1)->2
122	22->(1)->3
1225	25->(1)->5
12258	58->(2)->5
122587	87->(2)->5
（1）当相邻2个数字可以翻译	f(n) = f(n-1)+f(n-1)
（2）当相邻2个不可以翻译	f(n) = f(n-1)

1、在小于2位数时翻译方法就为1->1,1
2、在大于2位数的时候需要开始分情况讨论
（从第2位数开始就和前两位数有关）
若是 25>= tmp >=10 则与前两位数有关
否则翻译次数不会增加，比如125->1255只需判断125的种类即可

代码：

class Solution:
    def translateNum(self, num: int) -> int:
        nums = str(num)
        if len(nums)<2:
            return 1
        a = b = 1
        for i in range(2, len(nums) + 1):
            tmp = nums[i - 2:i]
            c = a + b if "10" <= tmp <= "25" else a
            b = a
            a = c
        return a
print(Solution().translateNum(12258))
#5
#可以精简一下，小于2的情况直接返回a，故最后代码为
class Solution:
    def translateNum(self, num: int) -> int:
        nums = str(num)#转换成字符串才能计算长度
        a = b = 1
        for i in range(2, len(nums) + 1):
            tmp = nums[i - 2:i]
            c = a + b if "10" <= tmp <= "25" else a
            b = a
            a = c
        return a
print(Solution().translateNum(12258))

解决！

2、继续进阶

??最长不含重复字符的子字符串
???????请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

???????哦吼，这题有意思，发现重复的数字便重新计算不就好了么，但是用什么记录呢？我首先想到的是哈希表，Python中`dic`便是哈希表，用哈希表记录位置。

#i获取字典中索引，j为字符循环位置
 a bcabcbb     #记录a位置，i不在字典中，索引指向-1
ij
 a b cabcbb    #记录b位置，i不在字典中，索引指向-1
i  j
 ab c abcbb    #记录c位置，i不在字典中，索引指向-1
i   j
 abc a bcbb    #此时a在字典中重复，更新字典位置，索引指向1，此时a的位置变化
 i   j             
 abca b cbb    #此时b在字典中重复，更新字典位置，索引指向1，此时b的位置变化
  i   j
 abcab c bb     
   i   j 
 abcabc b b     #字典继续更新，最近的b的位置是第二个abc中的b（上面已更新）
     i  j 
 abcabcb b      #更新最近的b的位置是倒数第二个b（上面又已更新）
       i j

这题的动态规划思想就比上一题浅一丢丢，但是难度上没有降低，因为他需要一个是否重复的判断容易想错->if tmp < j - i else j - i来判断出长度。逻辑有了，代码也就能通了。
代码：


class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        dic = {}
        res = tmp = 0
        for j in range(len(s)):
            i = dic.get(s[j], -1) # 获取索引 i
            dic[s[j]] = j # 更新哈希表
            tmp = tmp + 1 if tmp < j - i else j - i # dp[j - 1] -> dp[j]
            #print(i,dic,tmp)
            res = max(res, tmp) # max(dp[j - 1], dp[j])
        return res
print(Solution().lengthOfLongestSubstring('abcabccbb'))
#3
#这里借K神代码，没办法，自己写的代码不容易读懂
#出自：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/mian-shi-ti-48-zui-chang-bu-han-zhong-fu-zi-fu-d-9/