说下看完题后脑子里的第一手想法,感觉比较繁琐
原题dp[][]
第一个变种,再加一维dp[][][0~1]表示经过该点且是否使用过魔法,递推关系就多考虑一个向左或者向下过来的情况
dp[i][j][0] = dp[i+1][j][0] + dp[i][j - 1][0] dp[i][j][1] = dp[i+1][j][1] + dp[i][j - 1][1] + dp[i - 1][j][0] + dp[i][j + 1][0](合法情况下)
最后返回右上角dp[][][1]的值
第二个变种,同样是加限制条件[A][B]表示已经经过了A或B [AB]表示已经经过了[AB] []表示两个都没经过,然后根据条件筛选右上角dp的值
(好蠢的思路,空间开销巨大,而且一眼望过去变种2里的条件1和2好像是一个意思?是我考虑不全)