动态规划算法题：机器人到达指定合位置方法数

算法题：机器人到达指定合位置方法数

最近在看左程云的《程序员代码面试指南》，感觉不错，题都分了类，很方便有目的的刷题，书里的代码都是java实现的，刚好最近在学习python，就用python去练习一下。

1. 问题描述

假设有排成一行的N个位置，记为1~N，N大于等于2。开始时机器人在其中的M位置，机器人可以往左或往右，如果机器人来到1位置，那它只能往右到2位置，如果它来到N位置，那它只能往左到达N-1位置，规定机器人必须走k步，最终能够来到P位置的方法有多少种？给定N、M、K、P，返回方法数。

举例：

N=5，M=2，K=3，P=3,
一共5个位置，机器人最开始在2，位置上，走3步，来到3位置的方法有如下3种：
1)2->1,1->2,2->3
2)2->3,3->2,2->3
3)2->3,3->4,4->3
返回方法数3

N=3,M=1,K=3,P=3
不可能到达，所有返回方法数0.

2.解决方法

1）暴力递归：来到cur位置，如果cur==1 or N，下一步确定，后续剩下rest-1步，如果是1<cur<N，下一步可以走cur-1或cur+1，后续还剩rest-1步，所有可能走的方法都走一遍，如果最后能停在P，则走法+1。

2）动态规划：首先确定了walk方法是无后效性的，即现状态的返回值与怎么到达这个状态无关。然后确定可变参数：cur 和 rest，构造表。初始化这张表后，把表中数据计算完整。

3.代码实现

暴力递归算法：

 # 暴力递归
def walk(N, cur, rest, P):
    if rest == 0:
        if cur == P:
            return 1
        else:
            return 0
    
    if cur == 1:
        return walk(N, 2, rest-1, P)
    if cur == N:
        return walk(N, N-1, rest-1, P)

    return walk(N, cur-1, rest-1, P) + walk(N, cur+1, rest-1, P)


if __name__ == "__main__":
    N = int(input('Please input N:'))
    M = int(input('Please input M:'))
    K = int(input('Please input K:'))
    P = int(input('Please input P:'))

    if (N<2 or K<1 or M>N or P<1 or P>N):
        print('can not walk')
    else:
        print('There are {0} walkways'.format(walk(N, M, K, P)))

Please input N:5
Please input M:2
Please input K:3
Please input P:3
There are 3 walkways

动态规划算法：

def walkways(N, M, K, P):
    m = [[0 for i in range(N + 1)] for j in range(K + 1)]
    
    # 初始化
    m[0][P] = 1

    # 求解
    for i in range(2, N+1):
        for j in range(K+1):
            if j ==1:
                m[i][j] = m[i-1][j+1]
            elif i == N:
                m[i][j] = m[i-1][j-1]
            else:
                m[i][j] = m[i-1][j-1] + m[i-1][j+1]

    return m[K, P]


if __name__ == "__main__":
    N = int(input('Please input N:'))
    M = int(input('Please input M:'))
    K = int(input('Please input K:'))
    P = int(input('Please input P:'))

    if (N<2 or K<1 or M>N or P<1 or P>N):
        print('can not walk')
    else:
        # print('There are {0} walkways'.format(walk(N, M, K, P)))
        print('There are {0} walkways'.format(walk(N, M, K, P)))

Please input N:3
Please input M:1
Please input K:3
Please input P:3
There are 0 walkways
PS C:\users\tsg-user\Desktop\pythonpractice\算法题>  cd 'c:\users\tsg-user\Desktop\pythonpractice\算法题'; & 'C:\Users\tsg-user\AppData\Local\Programs\Python\Python38\python.exe' 'c:\Users\tsg-user\.vscode\extensions\ms-python.python-2020.6.91350\pythonFiles\lib\python\debugpy\launcher' '51958' '--' 'c:\users\tsg-user\Desktop\pythonpractice\算法题\机器人到达指定合位置方法数.py'
Please input N:5
Please input M:2
Please input K:3
Please input P:3
There are 3 walkways
PS C:\users\tsg-user\Desktop\pythonpractice\算法题>  cd 'c:\users\tsg-user\Desktop\pythonpractice\算法题'; & 'C:\Users\tsg-user\AppData\Local\Programs\Python\Python38\python.exe' 'c:\Users\tsg-user\.vscode\extensions\ms-python.python-2020.6.91350\pythonFiles\lib\python\debugpy\launcher' '51965' '--' 'c:\users\tsg-user\Desktop\pythonpractice\算法题\机器人到达指定合位置方法数.py'
Please input N:7
Please input M:4
Please input K:9
Please input P:5
There are 116 walkways
PS C:\users\tsg-user\Desktop\pythonpractice\算法题>
Please input N:65
Please input M:44
Please input K:25
Please input P:49
There are 3268760 walkways

最后这个算的时间有点长，不过相比暴力递归，还是快点多的多的

本文地址：https://blog.csdn.net/JYKgo/article/details/109891488