【每日一题】- 2020-09-14 -小兔的棋盘

[azl397985856]

小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!

比如对于 2*2 的棋盘， 有 C(4,2) = 6 种。

对于一个n*n的正方形网格，每次我们能向右或者向上移动一格，那么从左下角到右上角的所有在副对角线右下方的路径总数为C_n。同样引用Wikipedia上的一张图片来表示：

而题目限制了对角线不能跨越。这句话有必要解释一下， 就是说你从(0, 0)出发 到 (n, n) 的路径中，有横穿左上部分和右下部分。或者横穿右上部分和左下部分的视为不合格。

Input 
每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。

Output
对于每个输入数据输出路径数，具体格式看Sample Output。

Sample Input
1
3
12
-1

Sample Output
1 1 2
2 3 10
3 12 416024

[suukii]

代码

JavaScript Code

function test(n) {
    return catalan(n) * 2
}

function catalan(n) {
    if (n <= 1) return 1
    let res = 0
    for (let i = 0; i < n; i++) {
        res += catalan(i) * catalan(n - 1 - i)
    }
    return res
}

复杂度

• 时间复杂度：这种写法应该是 $O(2^n)$。
• 空间复杂度：$O(n)$。

[azl397985856]

DP

思路

如果可以跨越对角线，那么和 62. 不同路径 是一样的。

由于不能跨越对角线，因此我们可以走的路线大概就是：

由于图形是对称的， 因此我们求出一个边就够了， 直接乘以 2即可。 不妨以走下方为例：

此时如果 j < i ，那么就是不合法的（跨越了对角线），因为 j < i 都在图形的右上部分。其中 i 为横坐标， j 为总坐标。

值得一提的是，如果 n = 2， 实际上 x 和 y 方向我们都有三个点，而不是 2，这里需要注意下。

代码

from functools import lru_cache

@lru_cache(None)
def dp(i, j):
    if i == 0 and j == 0:
        return 1
    if i < 0 or j < 0:
        return 0
    if j < i:
        return 0
    return dp(i - 1, j) + dp(i, j - 1)

dp(n, n) * 2

复杂度分析

• 时间复杂度：$O(N^2)$
• 空间复杂度：$O(N^2)$

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经35K star啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

[RainStopsTonight]

学习了

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.