python-未名湖边的烦恼

解题思路:

这道题python写递归算法的话会超时，83分。

因此采用动态规划的解题方法。

建立一个(m+1)*(n+1)大小的二维数组dp[i][j]，其中dp[i][j]表示还鞋的有i个人借鞋的有j个人时满足题目要求的方法数。

初始化数组的值为0。

我们知道当借鞋的人数为0时，此时满足要求的排队方法只有一种，所以对于dp[i][0] = 1（i = 1 to m）。

①当i >j时，那么此时队伍的最后一个位置即可以是还鞋的人，也可以是借鞋的人。

如果是还鞋的人，我们可以假设最后一个人并不存在，对排列结果不会造成影响，此时的排列的可能数为dp[i-1][j]

如果是借鞋的人，我们也可以假设最后一个人并不存在，对排列结果不会造成影响，此时的排列的可能数为dp[i][j-1]

则dp[i][j] = dp[i-1][j] + dp[i][j-1]

②当i=j时，那么此时我们知道队伍的最后一个人一定是借鞋的人(这里略微思考一下应该能想明白)。

那么我们是不是就可以当最后一个借鞋的人不存在，对最后的结果也不会造成影响。

则dp[i][j] = dp[i][j-1]

③当i<j时，此时dp[i][j] = 0。

注意事项:

参考代码:

def f(m,n):  
    dp = [[0 for j in range(n+1)] for i in range(m+1)]  
    for i in range(1,m+1):  
        dp[i][0] = 1  
        for j in range(1,n+1):  
            if i > j:  
                dp[i][j] = dp[i-1][j]+dp[i][j-1]  
            elif i == j:  
                dp[i][j] = dp[i][j-1]  
      
    print(dp[m][n])  
          
  
m,n= map(int,input().strip().split())  
f(m,n)