今天看到有人在脉脉发公务员试题。题目如下：这道题数学上可以解，但是我已经辍学多年了。没有数学解决方案。但是一看到标题就想到可以用动态规划来解决这个问题。我们把“家”的位置标记为(0,0)，单位的位置标记为(4,3)，如下图所示：动态规划的一个典型解法就是在思考问题的时候逆向思考。假设现在我在单元(4,3)。我的最后一步在哪里？要到达(4,3)，只有两种方式，从(3,3)到(4,3)或从(4,2)到(4,3)。现在问题的规模缩小了，变成了两个小问题，一个是从家(0,0)到(4,2)有多少条路，另一个是从家(0,0)到(3),3)有多少种方式。至此，我们可以看出这其实是一个递归问题，即fn(x,y)=f(x-1,y)+f(x,y-1)。然而，这里要考虑的另一个问题是当我们处于fn(x,0)或fn(0,y)时。如果x>1，那么此时只有一条路可以走，就是从(x-1,0)到(x,0)。如果x==1，那么此时只能是从(0,0)到(1,0)。同样，对于(0,y)也是一样，如果y>1，那么只能从(0,y-1)到(0,y)。如果y==1，则仅从(0,0)到(0,1)。所以，按照这个思路，我们可以写出如下代码：deffind_walk_num(x,y):ify==0:ifx==1:return1returnfind_walk_num(x-1,0)ifx==0:ify==1:return1returnfind_walk_num(0,y-1)returnfind_walk_num(x-1,y)+find_walk_num(x,y-1)result=find_walk_num(4,3)print(f'从(0,0)走到(4,3)有一共有：{result}种')运行效果如下图所示：所以这道题的答案是D，一共有35种方式。
