过河卒是 CSP-J 经典 DP 题。

题目描述

棋盘上 (0,0) 到 (n,m)，只能向右或向下走。有一些控制点不能经过。求路径数。

解题思路

  • 状态定义：dp[i][j] = 从 (0,0) 走到 (i,j) 的路径数
  • 状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]
  • 初始状态：dp[0][0] = 1

常见错误

  • 忘记控制点本身也不能经过
  • 数据范围大，要用 long long

咨询 DP 学习：151 6522 2880