矩阵中的单调路径数（假递归）

本题即求(a+1)*(b+1)的矩阵中的单调路径数，即a*(b+1)的矩阵中的单调路径数与(a+1)*b的矩阵中的单调路径数之和。递归时可利用对称性。
另一种做法是直接推导出组合式并直接计算（略）。

def num_ways(num_rows, num_columns):
    num_rows += 1
    num_columns += 1
    # Java里用二维数组代替dict，也可以变二维为一维然后用Map
    _cache = {}
    def _sub(_rows, _columns):
        if _rows == 1 or _columns == 1:
            return 1
        try:
            return _cache[(_rows, _columns)]
        except KeyError:
            # 交换
            try:
                return _cache[(_columns, _rows)]
            except KeyError:
                row_result = _sub(_rows - 1, _columns)
                _cache[(_rows - 1, _columns)] = row_result
                column_result = _sub(_rows, _columns - 1)
                _cache[(_rows, _columns - 1)] = column_result
                return row_result + column_result
    return _sub(num_rows, num_columns)
#实在不知道给的数据格式到底怎样。。
_numbers = []
while True:
    try:
        inputs = [int(x) for x in input().split() if x.strip()]
        _numbers += inputs
    except:
        break
for i in range(0, len(_numbers), 2):
    num_rows, num_columns = _numbers[i], _numbers[i + 1]
    print(num_ways(num_rows, num_columns))