动态规划解决最值、有多少方案之类问题

问题一：最长不包含重复字符的子字符串剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣（LeetCode）

分析：dp[ i ] 代表以字符 s[ i ] 结尾的 最长不重复子字符串  的长度；对于 i，向前查找最近的相同字符 s[ j ] ,  s[ i ] == s[ j ] ;

　　　对于j，若其 < 0 , 则说明无相同字符，那么 dp[ i ] = dp[ i -1] + 1；

　　　若dp[ i -1] < i - j ;说明相同的字符在区间之外， 此时dp[ i ] = dp[ i -1] + 1；

　　　若dp[ i -1] >= i - j ，说明相同的字符 在区间之内，此时，dp[ i ] = i - j ；

　　针对第一种情况，可以合并到第二种情况中，因 j < 0 , dp[ i -1] < i 恒成立，那么dp[ i -1] < i - j 也成立。

思路1： 动态规划 + 线性遍历  

　　每一轮内，向前遍历最近的相同字符，此处 c 就相当于 dp[ i] ;节省空间

时间复杂度 ：O( N²)  ; 空间复杂度 ： O( 1);

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int a = 0;
        int c = 0;
        for(int i = 0;i < s.size(); ++i){
            int j = i -1;
            while(j >= 0 && s[j] != s[i]) --j;
            if(i - j > a) a += 1;
            else a = i - j; 
            c = max(c , a);
        }
        return c;
    }
};

思路2 ： 动态规划 + 哈希表

　　哈希表存放最后一次字符出现的位置，

时间复杂度 ：O( N)  ; 空间复杂度 ： O( 1);

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int>mp;
        int res = 0, tmp = 0,j = 0;
        for(int i =0;i < s.size(); ++i){
            if(mp.find(s[i]) == mp.end() ) j = -1;
            else j = mp[s[i]];
            mp[s[i]] = i;
            tmp = i - j > tmp ? tmp +1 : i - j;
            res = max(res,tmp);
        }
        return res;
    }
};

问题二：把数字翻译成字符串剑指 Offer 46. 把数字翻译成字符串 - 力扣（LeetCode）

分析：dp[ i ] 代表以字符 X_i 结尾的 翻译方案数量；考虑到 x_i 和  x_i-1 组成的两位数字可以被翻译；

　　　　当可以组合翻译时，除去x_i 和   x_i-1  ，前面的  x₀ - x_i-2 翻译方案为 dp[ i-2] ；当单独翻译时，除去   x_i ，前面的   x₀ - x_i-1 ，翻译方案数量为 dp[i-1] ,

　　　　组合翻译对应的数字区间为[10，25]，则 dp[ i ]  = dp[ i -1] + dp[ i -2] ；

　　　　　　　　　　　否则dp[ i ]  = dp[ i -1] ；

　　　　初始状态：dp[  0 ] = dp[ 1] = 1; 代表空数组和 一个 数字的翻译方案为1；

思路1 ： 字符串遍历，时间复杂度、空间复杂度都为O(N)

　　　　先将数字 num 转化为字符串 s； 字符串切片比较最后两个字符，与 字符 ‘1’ 或者‘2’  和 ‘5’，

class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num);
        int a =1,b=1;
        int c;
        for(int i = 2; i <= s.size(); ++i){
            string tmp = s.substr(i-2,2);
            if(tmp[0] == '1' || tmp[0] == '2' && tmp[1] <= '5') c = a +b;
            else c = a;
            b = a;
            a = c;
        }
        return a;
    }
};

思路2 ： 从右向左不断 取余 

class Solution {
public:
    int translateNum(int num) {
        int res = num % 10;
        num /= 10;
        int a = 1,b =1,c =0;
        while(num){
            int x = num % 10;
            num /= 10;
            int tmp = x * 10 + res;
            if(tmp >= 10 && tmp <= 25) c = a + b;
            else c = a;
            b = a;
            a = c;
            res = x;
        }
        return a;
    }
};