Create 62.不同路径(中等).md

JavaCodeMing · JavaCodeMing · commit 26315512d3d0 · 2020-08-24T20:36:15.000+08:00
diff --git a/Algorithm/62.不同路径(中等).md b/Algorithm/62.不同路径(中等).md
@@ -0,0 +1,38 @@
+```text
+��Ŀ:
+    һ��������λ��һ�� m x n ��������Ͻ�;
+    ������ÿ��ֻ�����»��������ƶ�һ��,��������ͼ�ﵽ��������½�;
+    ���ܹ��ж�������ͬ��·��?
+1.��̬�滮:
+    [1]˼·:
+        (1)dp[i][j]��ʾ��ԭ��(0,0)������λ��(i,j)��·���ܺ�;
+        (2)��Ϊֻ�����»�������,��˴�ԭ�㵽(i,j)��·���ܺ͵���ԭ�㵽(i-1,j)��·�ߵ��ܺͼ�ԭ�㵽(i,j-1)��·�ߵ��ܺ�;
+            ��˵õ���̬ת�Ʒ���: dp[i][j]=dp[i-1][j]+dp[i][j-1] (i>=1,j>=1)
+        (3)��i=0��j=0��������:
+            1)i=0��Ӧdp[0][j]��Ϊ��һ��,��ԭ�㵽(0,j)ֻ����һֱ����,����ֻ��һ��·��,��dp[0][j]=1;
+            2)j=0��Ӧdp[i][0]��Ϊ��һ��,��ԭ�㵽(i,0)ֻ����һ������,����ֻ��һ��·��,��dp[i][0]=1;
+    [2]ʵ��:
+        class Solution {
+            public int uniquePaths(int m, int n) {
+                int[][] dp = new int[m][n];
+                // ����һ��
+                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];
+                    }
+                }
+                return dp[m-1][n-1];
+            }
+        }
+    [3]���Ӷȷ���:
+        (1)ʱ�临�Ӷ�: O(m*n),mΪ����,nΪ����
+        (2)�ռ临�Ӷ�: O(m*n)
+```

-Original file line number
+Diff line change
@@ @@ -0,0 +1,38 @@ @@
 +```text
 +题目:
 +    一个机器人位于一个 m x n 网格的左上角;
 +    机器人每次只能向下或者向右移动一步,机器人试图达到网格的右下角;
 +    问总共有多少条不同的路径?
 +1.动态规划:
 +    [1]思路:
 +        (1)dp[i][j]表示从原点(0,0)到坐标位置(i,j)的路线总和;
 +        (2)因为只能往下或往右走,因此从原点到(i,j)的路线总和等于原点到(i-1,j)的路线的总和加原点到(i,j-1)的路线的总和;
 +            因此得到动态转移方程: dp[i][j]=dp[i-1][j]+dp[i][j-1] (i>=1,j>=1)
 +        (3)对i=0或j=0单独分析:
 +            1)i=0对应dp[0][j]即为第一行,从原点到(0,j)只能是一直往右,最终只有一条路径,即dp[0][j]=1;
 +            2)j=0对应dp[i][0]即为第一列,从原点到(i,0)只能是一致往下,最终只有一条路径,即dp[i][0]=1;
 +    [2]实现:
 +        class Solution {
 +            public int uniquePaths(int m, int n) {
 +                int[][] dp = new int[m][n];
 +                // 填充第一列
 +                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];
 +                    }
 +                }
 +                return dp[m-1][n-1];
 +            }
 +        }
 +    [3]复杂度分析:
 +        (1)时间复杂度: O(m*n),m为行数,n为列数
 +        (2)空间复杂度: O(m*n)
 +```