学习笔记

考虑使用动态规划。dp数组的意义是：dp[i][j]是从初始点到grid[i][j]的最小路径和。第一步，初始化，对第0行和第0列进行初始化，因为他们无法通过状态转移方程得到。第二步，状态转移方程为dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]

这个题采用动态规划的方法。我遇到的问题首先是：dp[i]表示的含义是什么？经过一番思考，我的dp[i]的含义是“子串[0,i]的解码方式”，在此基础上衍生出状态转移方程是由两部分组成的: 第一部分part1，这个part1是新增的s[i]单独编码时有多少种编码方式： 判断s[i]是否是'0'，若为0，则这个部分为0,因为s[i]不能单独编码;若不为0，则编码数量的dp[i-1] 第二部分part2，这个part2是s[i]与s[i-1]共同形成编码时有多少种编码方式： 判断s[i-1]s[i]形成的两位数是不是小于26且不会形成'0x'的形式，如果不会，为dp[i-2]，否则为0

于是基本完工，但是我这个方法的dp数组初始化比较麻烦，具体可以看代码，改了两三次才把他改对