算法练习--动态规划 相关

走方格的方案

请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

注：沿棋盘格之间的边缘线行走

输入描述：
输入两个正整数n和m，用空格隔开。(1≤n,m≤8)

输出描述：
输出一行结果

示例1
输入：
2 2
输出：
6

python实现：

• 递归
• 第一步向右 的方法数 + 第一步向下的方法数
• 类似爬楼梯

def func(n, m):if n < 0 or m < 0:return 0 # 没法走elif n == 0 or m == 0:return 1return func(n-1, m) + func(n, m-1)def walk():n, m = input().strip().split()n = int(n)m = int(m)return func(n, m)print(walk())

• 阶乘

import math
def walk():row, col = map(int, input().split())total_step = col + rowres = math.factorial(total_step) / (math.factorial(col) * math.factorial(row))print(int(res))walk()

• 动态规划
• 构造二维数组
• 每个点的方法数= 上面点 + 左边点 方法数之和

def walk():n,m = map(int, input().split(' '))dp = [[1 for i in range(n+1)] for j in range(m+1)]for i in range(1,m+1):for j in range(1,n+1):dp[i][j] = dp[i-1][j]+dp[i][j-1]print(dp[m][n])walk()