疯狂的动态规划
- 2020 年 12 月 17 日
- AI
让我们比较一下普通人的直观思路和动态规划的“动态思路”，直观的思路一般都是暴力循环，例如距一个简单的例子：
“1225”
直观思路就是，分类讨论：
一共4个字母，那么我们有这么几种选择：
1、4个数字直接翻译；
2、两个数字单独翻译，剩下两个数字合并翻译；
3、两个数字合并翻译，另外两个数字还是合并翻译
4个数字直接翻译比较简单，只有一种情况，即1、2、2、5直接翻译为对应字母；
两个数字单独翻译，稍微复杂一些，我们要去遍历，假设1-2位合并翻译，2-3位合并翻译，3-4位合并翻译，则一共有3种情况，同时需要去判断合并的两位数是否可以正常翻译；
最后一种情况也比较简单，只有两种情况，1-2位合并翻译，3-4位合并翻译同时判断是否可以正常翻译；
解决这类问题直观的思路就是分类讨论，也是我们高中的时候比较常用的一些解题技巧，但是显然，当问题变得更加复杂的时候，例如”12233445566″，这种情况下我们去分类讨论的话，整个问题的解决起来非常的棘手，例如字符串的长度为100，则怎么分情况讨论。。。合并翻译取几次，一次可以，两次可以，三次可以。。。。50次可以，除此之外合并翻译一次，就有99种组合了，1-2，2-3，3-4，4-5，。。。。99-100，如果是合并翻译两次，则假设第一次是1-2合并翻译，则第二次合并翻译的情况有，2-3，3-4，4-5.。。。。99-100，有98种组合。。。。依次类推，整个问题从人类逻辑上来解决就非常麻烦了，使用编程语言实现就更加复杂而冗余了，这个时候，就应该想到动态规划的方法；
动态规划的思路和分类讨论的思路完全不同，个人的直观感受是，这很像找规律的问题，动态规划不是从全量数据上去做考虑，而是从局部开始考虑（找规律），比如对于一个复杂的字符串：”123456789″，使用dp的方法是，先把问题当作简单问题处理，即比如我们先取前面的1位，“1”,显然只有1种组合；
然后是“12”，这种情况很好计算，1、2分开翻译的情况有（1、2）有1种组合，或者1-2合并翻译的i情况有（1-2）一种，一共2种组合；
然后我们再考虑“123”，1、2、3分开翻译的情况有（1、2、3）1种组合，然后就剩下一次合并翻译+一次单独翻译，情况有（1，2-3），（1-2，3）2种情况，一共3种情况；
最后考虑“1234”，1、2、3、4分开翻译的情况有（1，2，3，4）1种组合，然后是（1-2，3，4），（1，2-3，4），（1，2，3-4），（1-2，3-4）一共4种组合，则一共有5种情况；
这样举了4个例子之后我们就发现规律了：
1、2、3、5,显然第n个数是第n-1和第n-2个数之和（这里为了理解的简单暂时不考虑无法翻译的情况，无法翻译加一个条件判断就可以了）
那么这里简单的递推公式我们就能写出来了：
f(n)=f(n-1)+f(n-2)
也就是我们所谓的“转移方程”
如果这道题没有加不能翻译的限制，而是无论2位数字怎么组合都可以成功翻译，那么这一题到这里就结束了：
class Solution:
def translateNum(self, num: int) -> int:
lens = len(str(num))
fn_2=1 #表示n-2位对应的f函数值这里是初始状态
fn_1=2 #表示n-1位对应的f函数值这里是初始状态
res=[0]*lens
res[0]=fn_2
res[1]=fn_1
for i in range(2, lens):
res[i]=res[i-1]+res[i-2]
return res[-1]这里为了好理解单独把fn_1,fn_2表示出来，这样用动态规划解决问题的小思路就出来了，然后就是常见的用动态数组（或者说滑窗，slide windows之类的）将空间复杂度降下来；
其实这是两个知识点，对于动态规划不熟悉的人（比如我）来说，初期接触太多算法组合在一起的问题就觉得烦躁不安，get不到重点的感觉，所以分拆来逐个击破是比较好的理解方式：
使用动态数组的思路是比较好理解的，因为我们的fn只和fn_1与fn_2有关，所以我们仅需要保留fn_1与fn_2这两个数字就可以了，此时空间复杂度就从O(n)（我们初始new了一个长度为n的res数字）变成O(1)（只需要保存两个数字fn_1和fn_2就可以）；
class Solution:
def translateNum(self, num: int) -> int:
lens = len(str(num))
fn_2=1 #表示n-2位对应的f函数值这里是初始状态
fn_1=2 #表示n-1位对应的f函数值这里是初始状态
for i in range(2, lens):
fn_2,fn_1=fn_1,fn_1+fn_2
return fn_1这样的话，我们理解原始的问题就简单多了，
首先我们得到初始状态,以“123456789”为例
f(0)=f(‘1’)=1
f(1)=f(’12’)=2
那么f(2)=f(‘123’)=1+2=3=f(‘1′)+f(12’)
f(3)=f(‘1234′)=f(’12’)+f(‘123’)=2+3=5
整个解决问题的思路如上，
按照我们上面的思路
class Solution:
def translateNum(self, num: int) -> int:
s = str(num)
res=[0]*(len(s)+1)
res[0]=1 #两个初始状态
res[1]=1
for i in range(2, len(s) + 1): #因为左闭右开的问题，这里i要取到len(s)+1才行
tmp = s[i - 2:i]
if "10" <= tmp <= "25":
res[i]=res[i-1]+res[i-2]
else:
res[i]=res[i-1]
return res[-1]上述代码有两个坑比的边界问题需要注意：
1、边界条件的坑：关于字符串S，遇到边界条件判断默念，左闭右开左闭右开左闭右开，当我们需要取最后两位的时候，比如字符串是”12345″，则如果我们要取“45”，需要tmp=s[i-2:i]=s[3:5]
则我们循环的上界必须是6即len(s)+1。。。这些边界真的恶心啊。。。考验专注和细节。。。
2、输入特殊情况的坑：如果我们假设两个数字的组合无论如何都可以翻译则没有这个坑，但是这一道题需要判断2个数字的组合是否小于“10”或者大于“25”，这个地方比较坑，因为这样的话：
res[0]=1 没有问题，一个数字还是只能对应一种翻译情况；
res[1]=2 就出现问题了，如果我们的第一位和第二位数字的组合是65,78之类的，则res[1]=1;
那么这种情况下就需要去if else判断了，if s[0:2] balabalabala
显然，当你的程序中出现了很多if else的时候，你就需要考虑对其进行优化了，一段优雅的代码里不应该有这么多的条件判断语句的出现。这里原作者给的思路很灵活：
从 s的-1位开始计算；
res[0]表示s[-1]用1来填充；
res[1]表示s[0]=1
则当我们从index=2开始的时候，s[0:2]的判断可以包含到后面的s[1:3],s[2:4]。。。。的判断中去了，具体过程可见
这里的动态图解;
然后还是一样做空间复杂度的优化，我们的时间复杂度是O(n)，目前空间复杂度也是O(n)，通过动态数组实现，因为我们每次f(n)的结果都只和f(n-1)和f(n-2)有关，因此只需要对这二者进行存储即可：
class Solution:
def translateNum(self, num: int) -> int:
s = str(num)
a = b = 1
for i in range(2, len(s) + 1):
tmp = s[i - 2:i]
c = a + b if "10" <= tmp <= "25" else a
b = a
a = c
return a变态小青蛙跳台阶问题，算是最简单的动态规划问题了：
假设初始状态为0，f(0)=1
然后是跳1级台阶为1，f(1)=1
f(2)=2
f(3)=3
f(4)=5
。。。。。递归公式非常简单就写出来鸟：
f(n)=f(n-1)+f(n-2)
class Solution:
def numWays(self, n: int) -> int:
if n==0:
return 1
res=[0]*(n+1)
res[0]=1
res[1]=1
for i in range(2,n+1):
res[i]=res[i-1]+res[i-2]
if res[i]>1000000007:
res[i]=res[i]%1000000007
return res[-1]难度低，就是边界和特殊输入，需要好好注意一下
内存优化的思路就是动态数组：
class Solution:
def numWays(self, n: int) -> int:
if n==0:
return 1
a=1
b=1
for i in range(2,n+1):
a,b=b,a+b
if b>1000000007:
b=b%1000000007
return b斐波那契数列这种经典的动态规划就不用多说了。。。
class Solution:
def fib(self, n: int) -> int:
if n==0:
return 0
fn_2=0
fn_1=1
for i in range(2,n+1):
temp=fn_1+fn_2
if temp>1000000007:
temp=temp%1000000007
fn_2=fn_1
fn_1=temp
return fn_1可以看到套路基本是 一样的，朴素的方法就是new一个n+1的数组，空间复杂度优化就用动态数组，然后注意边界条件和一些额外的条件就行了；
最后是问题扩展到矩阵，这也是一种很典型的题型。。面试碰到好几次了wtf
这道题相对于剪绳子的问题要简单一些，我们从最后一步开始看，因为我们最终必然是到达右下角的点停止的，因此从右下角的点开始看：
f(i,j)=max(f(i-1,j),f(i,j-1))+matrix[i][j] ##这就是我们的状态转移方程（规律公式了）
以上面的例子为例，f(2,2)(2,2表示右下角的点的坐标，python的下标从0开始时刻记住)的值为：
f(2,2)=max(f(2,1),f(1,2))+matrix(2,2)
根据我们的状态转移方程：
f(i,j)=max(f(i-1,j),f(i,j-1))+matrix[i][j]
可以看到i和j都要从1开始，因此对于i和j分别为0的情况，即对应grid的第0行和第0列，我们需要先进行计算作为我们的初始状态值，这里和之前的初始状态不太相同，对于数组来说，初始化一般比较常见的形式是两个数字，f0，f1，而对于矩阵来说，初始的形式是一对行列，即第0行和第0列的所有数字都根据实际需要的计算进行初始化：
class Solution:
def maxValue(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
for j in range(1, n): # 初始化第一行
grid[0][j] += grid[0][j - 1]
for i in range(1, m): # 初始化第一列
grid[i][0] += grid[i - 1][0]
for i in range(1, m):
for j in range(1, n):
grid[i][j] += max(grid[i][j - 1], grid[i - 1][j])
return grid[-1][-1]考虑到：
剪绳子1，2与正则表达式这三题出现的频率较低，暂时就不看了。。。先看看高频题吧
除了这三题，剑指offer的动态规划题就都完成了
