Day 29 动态规划part02| LeetCode 62.不同路径，63.不同路径II

62.不同路径

62. 不同路径

class Solution {
        public int uniquePaths(int m, int n) {

            int [][]dp=new int[m][n];
            //dp数组 -- dp[i][j] 达到坐标(i,j)有几种路径
            //dp数值初始化-- 终点为：dp[m-1][n-1]
          
            for(int i=0;i<m;i++)
            {
                dp[i][0]=1;
            }
            for(int j=0;j<n;j++)
            {
                dp[0][j]=1;
            }

            //确定遍历顺序--


            for(int i=1;i<m;i++)
            {
                for(int j=1;j<n;j++)
                {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
            //打印dp数组
            return dp[m-1][n-1];
        }
    }

63.不同路径II

63. 不同路径 II

 class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
          int m=obstacleGrid.length;
          int n=obstacleGrid[0].length;

            //dp数组 -- dp[i][j] 达到坐标(i,j)有几种路径
            int [][]dp=new int[m][n];

            if(obstacleGrid[m-1][n-1]==1||obstacleGrid[0][0]==1)return 0;

            //dp数值初始化-- 终点为：dp[m-1][n-1]
         
            for(int i=0;i<m&&obstacleGrid[i][0]==0;i++)
            {
             
                    dp[i][0]=1;
                
            }

            for(int j=0;j<n&&obstacleGrid[0][j]==0;j++)
            {
             
                    dp[0][j]=1;
                

            }

            //确定遍历顺序--

            for(int i=1;i<m;i++)
            {
                for(int j=1;j<n;j++)
                {
                    
                    if(dp[i-1][j]+dp[i][j-1]!=0&&(obstacleGrid[i][j] ==0))
                    {
                        dp[i][j]=dp[i-1][j]+dp[i][j-1];
                    }
 

                }
            }
            //打印dp数组

            return dp[m-1][n-1];
        }
    }

343.整数拆分（1刷略）

96.不同的二叉搜索树（1刷略）