3.27网易互联网笔试动态规划题解-类比剑指

题目描述：（第二题）
给一个小写字母字符串。
可以标记的条件：相邻两个字母为相同字母，或者是字母表中的相邻字母，例如“aa” "ba" "st"可以被标记，"ad" 不可以被标记
a为1分，b为2分，以此类推
一个字母只能被标记一次。求最高分数。
输入：abb 输出：4
输入：abgcc 输出：a1+b2+c3+c3 = 6
思路：动态规划：
map 映射 字母与序号的关系。
dp[i] 表示以 i 结尾的最大分数

• 当 s[i] 和 s[i-1] 不相邻
  dp[i] = dp[i-1]
• 当 s[i] 和 s[i-1] 相邻
  要么取倒数两位，要么取之前的不变
  dp[i] = Math.max(dp[i],dp[i-2]+map.get(s[i-1])+map.get(s[i-2])

注意：考虑动态规划，只需要依次动归，不需要太复杂地考虑条件了
主动使用 Math.max 方法呀。

// 哈希表
let map = new Map([["a",1],["b",2],....["z",26]]);
// 判断两个字符是否字母表相邻
function closed(i,j){
  return Math.abs(map.get(i)-map.get(j))<=1;
}
function maxClosed(s){
  if(s.length<=1) return 0;
  let dp=[];
  dp[0] = 0;
  if(closed(s[0],s[1])){//前两位相邻
    dp[1] = map.get(s[0]) + map.get(s[1]);
  }else{// 前两位不相邻
   dp[1] = 0;
  }
  for(let i=2;i<s.length;i++){
    if(closed(s[i],s[i-1])){// i-1和i是相邻字符
      dp[i] = Math.max(dp[i-1],dp[i-2]+map.get(s[i-1])+map.get(s[i-2]))
    }else{// i-1和i不是相邻字符
      dp[i] = dp[i-1]
    }
  }
}

剑指 Offer 46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法
dp[i] 以 i 结尾的翻译方法数。

• s[i]+s[i-1] 属于 [10, 25]
  把最后一个数字当做一个字母翻译：dp[i] = dp[i-1]
• s[i]+s[i-1]不属于 [10, 25]
  25—>z 或者 cf
  可以把最后2个数字当做2个字母翻译 + 也可以把最后2个数字当做一个字母翻译：
  dp[i] = dp[i-1] + dp[i-2]

var translateNum = function(num) {
    if(num<=1) return 1;
    let s = num+"";
    let dp = [];
    dp[0] = 1;
    // 初始化 dp 列表
    if((s[0]+s[1])*1>=10&&(s[0]+s[1])*1<=25){
        dp[1] = 2;
    }else{
        dp[1] = 1;
    }
    // 动态规划
    for(let i=2;i<s.length;i++){
        if((s[i-1]+s[i])*1>=10&&(s[i-1]+s[i])*1<=25){
            dp[i] = dp[i-1] + dp[i-2]
        }else{
            dp[i] = dp[i-1];
        }
    }
    return dp[dp.length-1];
};