华为09-06笔试 部份题解（期望步数）

三面都过了，泡池子中，求offer

第一题简单题
第二题题目真读不懂 乱写
第三题概率+dp 测试用例比较弱

1. n 个个字符串，一个数字, 一个匹配字符串，每个字符串中的字符小于那个数字就作为特征值 , 然后判断和匹配字符串的特征值相同（或者包含关系）的字符串 .
   ex. 字符串 数字 -> 特征
   "239123" "3" -> "212"
   这题比较简单，注意读入，输出和包含关系（用contains不要用equals）就行

2. 编辑距离？完全不懂，感觉给的用例都是错的。

"This is a book!" 和 "This is book!" 差值为 1
"This is a book!" 和 "This is book" 差值也为 1 ??? （符号差一，单词差一，不应该2吗）

"This is a book!" 和 "This is a duck" 差值为 2
"is This a book!" 和 "is this a book?" 差值为 1 ??? (说了符号和单词一样的算)

直接hashmap乱写一通，顺序都不考虑了，拿了40%， 放弃

3. m*n 矩阵，求从左上角到右下角的步数期望，每个格子往下往右原地不动的概率分别为PD，PR，PS.
   dp[i][j] 表示 从（i，j）到终点的期望步数

   dp[i][j] = 1 + PD * dp[i+1][j] + PR * dp[i][j+1]  + PS * dp[i][j] 
   dp[i][j] = ( 1 + PD * dp[i+1][j] + PR * dp[i][j+1] ) / (1 - PS)

   （i，j） 只依赖 i+1 and j+1 ，满足动态规划的性质

• 从下往上
  • 从右往左
    • dp就ok

本来以为有很奇怪的出界的case，提交看看就过了

三面都过了，等池子中