प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

62. भिन्नाः मार्गाः

• मम कोडः (त्रुटिप्रतिवेदनम्) .
  लेखनप्रक्रियायाः समये ये बिन्दवः अहं बहु भ्रमितः अनुभवामि: 1 द्वि-आयामी-सरण्याः अस्य प्रश्नस्य च पत्राचारः स्पष्टः नास्ति किम् mn dp[m][n] अथवा dp[n][m] 2 इत्यस्य आरम्भः अस्ति

class Solution {
    public int uniquePaths(int m, int n) {
        int[][]dp = new int[m+1][n+1];
        dp[0][0] = 0;
        dp[0][1] = 1;
        dp[1][0] = 1;
        for(int i=1; i<m; i++) {
            for(int j=1; j<n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }
}

/*
自己解题的时候思考过程

n-1 : 往右走的次数
m-1 : 往下走的次数 

dp[i][j]到当前的位置，有几种方法
dp[0][0] 0
dp[0][1] 1
dp[1][0] 1
dp[1][1] 2
dp[i][j] 的前一个状态是，(1)他的左边dp[i-1][j]，或者(1)dp[i-1][j-1]
dp[i][j] = dp[i-1][j] + dp[i-1][j-1];

 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

अत्र आरम्भदोषः सम्पूर्णं वामस्तम्भं क्षैतिजपङ्क्तिं च आच्छादयितुं आवश्यकम् ।

// 第0列，dp[i][0] 表示到当前的位置，有几种方法，这一列都是只有一种
 for (int i = 0; i < m; i++) {
  dp[i][0] = 1;
 }
 
// 第0行，dp[0][i] 表示到当前的位置，有几种方法，这一行都是只有一种
 for (int i = 0; i < n; i++) {
     dp[0][i] = 1;
 }
1
2
3
4
5
6
7
8
9

जावा द्वि-आयामी सरणी भण्डारणचित्रम् : १.

• विचार प्रक्रिया
  (1) dp array तथा subscripts इत्यस्य अर्थं निर्धारयन्तु :到当前的位置[i][j]，有几种方法 dp[i][j]
  (2) पुनरावृत्तिसूत्रं निर्धारयतुdp[i][j] = dp[i-1][j] + dp[i][j-1];
  (3) dp array इत्यस्य आरम्भः कथं भवति本题就栽在这一步了，其实是要for循环 初始化一列和一排的
  (4) अग्रे पृष्ठतः पारगमनक्रमं निर्धारयन्तु
  (5) dp सरणीं व्युत्पादयितुं उदाहरणस्य उपयोगं कुर्वन्तु
  (6) dp सरणी मुद्रयन्तु

• ac

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 i=0; i<n; i++) {
            dp[0][i] = 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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

जवा

द्विविधस्य सरणीयाः दीर्घतां ज्ञातव्यम्

int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
1
2

63. भिन्नाः मार्गाः II

• सूत्रं व्युत्पन्नं कुरुत dp[i][j] = dp[i-1][j] + dp[i][j-1];
  यदि [इ][ज] बाधकं स्यात् तर्हि गमनम् असम्भवं स्यात्।
  if(obs[i][j] == 0) dp[i][j] = dp[i-1][j] + dp[i][j-1];

• आरम्भीकरणम्
  यदि प्रथमपङ्क्तौ वा स्तम्भे वा बाधा अस्ति तर्हि अनन्तरं सर्वे 0 इति आरभ्यन्ते ।

• त्रुटि

java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 3
  at line 22, Solution.uniquePathsWithObstacles
  at line 56, __DriverSolution__.__helper__
  at line 86, __Driver__.main
1
2
3
4

यतः dp [1][1] तः आरब्धः ।

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

        int[][]dp = new int[m][n];
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
            return 0;
        } 
        //初始化
        for(int i=0; i<m && obstacleGrid[i][0]!=1; i++) {
            dp[i][0] = 1;
            //中途如果有obstacleGrid[i][0]!=0，那就暂停循环，Java初始化都赋了0
        }

        //初始化
        for(int j=0; j<n && obstacleGrid[0][j]!=1; j++) {
            dp[0][j] = 1;
        }
        for(int i=1; i<m; i++) { //这里写了0是错误的
            for(int j=1; j<n; j++) {
                dp[i][j] = (obstacleGrid[i][j]==0?(dp[i][j-1]+dp[i-1][j]):0);
            }
        }
        return dp[m-1][n-1];
    }
}

//我的思考
// obstacleGrid[i][j] = 1 此处有障碍物，走不了
// obstacleGrid[i][j] = 0
// dp[i][j] = dp[i-1][j] + dp[i][j-1]
// 如果 obstacleGrid[i-1][j] = 1，前一种状态就不能是dp[i-1][j]，dp[i][j] = dp[i][j-1]
// 如果 obstacleGrid[i][j-1] = 1，前一种状态就不能是dp[i][j-1]，dp[i][j] = dp[i-1][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

343. पूर्णाङ्कविभाजनम्

न विचारः

समस्यानिराकरणविचारेषु ध्यानं दत्तव्यम्
1 यथासम्भवं समानसङ्ख्यासु विभज्य यदा सर्वाणि विभक्तसङ्ख्यानि समानानि भवन्ति तदा उत्पादः बृहत्तमः भविष्यति। २ इष्टतमः विभाजनसङ्ख्या ३ अस्ति ।

• गणितीय पद्धति

class Solution {
    public int integerBreak(int n) {
        if(n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if(b == 0) return (int)Math.pow(3, a);
        if(b == 1) return (int)Math.pow(3, a - 1) * 4;
        return (int)Math.pow(3, a) * 2;
    }
}
1
2
3
4
5
6
7
8
9

• गतिशील प्रोग्रामिंग ?
  किञ्चित् न अवगच्छामि

96. भिन्नाः द्विचक्रीय अन्वेषणवृक्षाः