动态规划： dynamic programming
名字看起来很高大上，也不知道动态在哪里，做了一些题目，看了一些解释，感觉就是
1 减少重复计算，
2 有点递归的味道，首先从后往前推出状态方程，然后从前往后写出dp数组
3 也有点高中数学归纳法的味道，新的值是由旧的值得到的

今晚做的是 力扣 Offer 46. 把数字翻译成字符串
记录一下这一题的思路，虽然都是评论区老哥老姐的杰作，但是看懂了，自己也重新码了一遍，顺带更多的理解动态规划的一般套路。

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

一般来说就是使用dp数组存储最终的结果，假设已经知道了dp[i-1],求dp[i]
dp[i-1]: 前i-1个数的最大翻译方案数
设新增加的数字为c,它的左边一位数字为b
如果bc不能翻译成一个字符的话，那么 dp[i]=dp[i-1]
如果bc可以翻译成一个字符的话，那么 dp[i]=dp[i-2]+dp[i-1]

至此就求出了状态转移方程

然后就是初始值的确定：
首先dp[1]=1是一定的，因为只有一个字符
那么dp[2]=1或者dp[2]=2 因此就要求dp[0]=1的
于是采用动态规划的思路就是：
每次新增一位数，算出对应的翻译种类数量

然后，为了取出每一位数字，这里又有两种方法去得到：

  1. 从右往左计算，通过num除以10控制循环长度，以及对10取余得到最右边的一位数
  2. 通过将数组转换为字符串，然后使用string的两个子函数
    string.substr();得到子字符串
    string.compare();比较字符串，比较字符串的时候会一位一位的比较，如果有一位比较小，那么结果就是负数；如果前面几位一样，字符串比较长的那一个就比较大

    一共提交了三次：
    1 申请了dp[A.size()+1]
    2 优化了dp,只存储两个值
    3 利用取余的方式，优化到string的空间

    怎么感觉内存没有多少变化呢！！！！！
    太热了 明天一定少穿一点 ！！！！！！