题解 | #挤奶路径#
挤奶路径
https://www.nowcoder.com/practice/6ab56cedae0646e19fb64b8bdbad82a6
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cows int整型二维数组 * @return int整型 */ public static int uniquePathsWithObstacles (int[][] cows) { // write code here int[][] arr = new int[cows.length][cows.length]; int m=0; int n=0; while(m<cows.length || n<cows.length){ if(m<cows.length && cows[0][m]!=1){ arr[0][m]=1; m++; }else{ while(m<cows.length){ arr[0][m]=0; m++; } } if(n<cows.length && cows[n][0]!=1){ arr[n][0]=1; n++; }else{ while(n<cows.length){ arr[n][0]=0; n++; } } } for(int i=1;i<arr.length;i++){ for(int j=1;j<arr.length;j++){ if(cows[i][j]==1){ arr[i][j]=0; }else{ arr[i][j]=arr[i-1][j]+arr[i][j-1]; } } } return arr[arr.length-1][arr.length-1]; } }
本题考察的知识点是动态规范,所用编程语言是java.本题的难点是多了个障碍物在网格中,由于多了障碍物,所以我们需要考虑更多的情况,考虑障碍物情况如下:
1.障碍物在边界时,则在障碍物之后的位置都无法到达,边界位置是第一行或者第一列
2.障碍物不在边界时,则此处设置路径数为0
该位置不存在障碍物时,对于没有障碍物的位置,情况如下:
1.位置在边界时,设为路径数为1
2.位置不在边界时,路径数为上一行同一列位置和同一行靠左位置路径数之和
综上就是算法动态规范我们需要考虑的注意事项。