题意:在一个 n×n 的 01 矩阵中,从 (1,1) 只能向下或向右走,到达 (n,n) 为止;统计路径上 0 的个数与 1 的个数的绝对差值≤k 的所有路径条数,答案对 1e9+7 取模。
相关算法:动态规划(DP)
核心思路
小O有一个 n×n 的 01 矩阵 a 。矩阵从上往下为第 i 行,从左往右为第 j 列。初始时位于 (1,1),每次移动能向下或者向右移动一个格子,前提是不能移出边界。
每到一个位置得到该位置的元素,到达 (n,n) 后停止移动,请你计算共有多少条路径满足 0 的数量和 1 的数量的绝对差值小于等于 k ,由于结果可能很大,对 (109+7) 取模后输出。
第一行两个整数 n,k(1≦n≦200,0≦k≦2×n−1),表示矩阵的长宽大小和路径中 01 数量的绝对差值限制。
输出一个整数,表示满足条件的路径总数,结果对 (109+7) 取模。
输入
3 2
010
000
110
输出
2