其实这张照片整幅都是画出来的。。。# Joke - 肚皮舞运动
v*a
1 楼
Dynamic Programming.
Define:
C[i][j], Pascal Triangle
C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
G[i][stp]: 只看第 i dimension，走了 stp 步，总共的可能情况
G[i][j] = Need another utility function
T[pos][stp]: 只看第 i dimension, 从 pos 出发，走 stp 步，总共的可能情况
T[pos][stp] = T[pos + 1][stp - 1] + T[pos - 1][stp - 1]
Then
G[i][j] = T[start_i][j], start_i 第i dimension的starting point
F[i][j]: 只考虑前i dimension, 走了j step，总共的可能情况, then
F[i][j] = F[i - 1][k] * G[j - k] * C(j, j - k) | for k = 0 to j (inclusive)
Answer: F[N][M]
Tips:
1) use (...)% Mod everywhere, Mod = 1000000007L
2) use long long everywhere
3）一般 Dimension 相关的题目都符合 DP 的前提，每个 Dimension 互不干扰
4）一般 计数 问题很可能是 DP，特别是result非常大，需要 Mod 10000000007 的这
种，不用DP保存状态，每次都Mod一下，很难一次得到result的
Define:
C[i][j], Pascal Triangle
C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
G[i][stp]: 只看第 i dimension，走了 stp 步，总共的可能情况
G[i][j] = Need another utility function
T[pos][stp]: 只看第 i dimension, 从 pos 出发，走 stp 步，总共的可能情况
T[pos][stp] = T[pos + 1][stp - 1] + T[pos - 1][stp - 1]
Then
G[i][j] = T[start_i][j], start_i 第i dimension的starting point
F[i][j]: 只考虑前i dimension, 走了j step，总共的可能情况, then
F[i][j] = F[i - 1][k] * G[j - k] * C(j, j - k) | for k = 0 to j (inclusive)
Answer: F[N][M]
Tips:
1) use (...)% Mod everywhere, Mod = 1000000007L
2) use long long everywhere
3）一般 Dimension 相关的题目都符合 DP 的前提，每个 Dimension 互不干扰
4）一般 计数 问题很可能是 DP，特别是result非常大，需要 Mod 10000000007 的这
种，不用DP保存状态，每次都Mod一下，很难一次得到result的
