题解 | 机器人达到指定位置方法数

package main

import (
	"fmt"
)

func main() {
	N, M, K, P := 0, 0, 0, 0
	for {
		n, _ := fmt.Scan(&N, &M, &K, &P)
		if n == 0 {
			break
		} else {
			fmt.Println(process(N, M, K, P))
		}
	}
}
func process(n, m, k, p int) int {
	// if k == 0 {
	// 	if m == p {
	// 		return 1
	// 	} else {
	// 		return 0
	// 	}
	// }
	// sum := 0
	// if m-1 > 0 {
	// 	sum += process(n, m-1, k-1, p)
	// }
	// if m+1 <= n {
	// 	sum += process(n, m+1, k-1, p)
	// }
	// return sum

	// 时间o(n*k), 空间o(n*k)
	// dp := make([][]int, k+1)
	// for i := 0; i < len(dp); i++ {
	// 	dp[i] = make([]int, n+1)
	// }
	// dp[0][p] = 1
	// for i := 1; i <= k; i++ {
	// 	for j := 1; j <= n; j++ {
	// 		if j-1 > 0 {
	// 			dp[i][j] += dp[i-1][j-1]
	// 			dp[i][j] = dp[i][j] % (1e9 + 7)
	// 		}
	// 		if j+1 <= n {
	// 			dp[i][j] += dp[i-1][j+1]
	// 			dp[i][j] = dp[i][j] % (1e9 + 7)
	// 		}
	// 	}
	// }

	// return dp[k][m]

	// 时间o(n*k), 空间o(n)
	dp := make([]int, n+1)
	dp[p] = 1
	prejbefore := 0
	for i := 1; i <= k; i++ {
		for j := 1; j <= n; j++ {
			add := prejbefore
			// 更新前保留
			prejbefore = dp[j]
			dp[j] = add
			if j+1 <= n {
				dp[j] += dp[j+1]
				dp[j] = dp[j] % (1e9 + 7)
			}

		}
	}

	return dp[m]
}