题目
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1 输出：3
示例 2：
输入：m = 3, n = 1, k = 0 输出：1
解题
方法一：动态规划
和leetcode-62：不同路径、leetcode-63：不同路径 II一样的方法，只不过，在每个格子上面增加了 判断格子所在行列坐标数位之和是否小于k（isValid）.
class Solution { public: //判断格子所在行列坐标数位之和是否小于k bool isValid(int row,int col,int k){ int res=0; while(row>0){ res+=row%10; row/=10; } while(col>0){ res+=col%10; col/=10; } return res<=k; } int movingCount(int m, int n, int k) { int res=0; vector<vector<bool>> dp(m,vector<bool>(n,false));//定义dp数组 for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ //起始点 if(i==0&&j==0){ res++; dp[i][j]=true; } //第一行,只能由左侧格子推出 else if(i==0&&j>0&&dp[i][j-1]&&isValid(i,j,k)){ res++; dp[i][j]=true; } //第一列，只能由上侧格子推出 else if(i>0&&j==0&&dp[i-1][j]&&isValid(i,j,k)){ res++; dp[i][j]=true; } //非第一行或第一列，由左侧或上侧的格子推出 else if(i>0&&j>0&&(dp[i-1][j]||dp[i][j-1])&&isValid(i,j,k)){ res++; dp[i][j]=true; } } } return res; } };
