JAVA | 100% Fast| Iterative DP
Similar to @useliuqing\'s solution, but iterative fashion.. all credits to @useliuqing \n\nclass Solution {\n    public String kthSmallestPath(int[] destination
Similar to @useliuqing\'s solution, but iterative fashion.. all credits to @useliuqing \n```\nclass Solution {\n    public String kthSmallestPath(int[] destination, int k) {\n        //create a dp of how many ways to reach destination from present row and col\n      int rows = destination[0];\n      int cols = destination[1];\n      \n      int[][] dp = new int[rows+1][cols+1];\n      \n      Arrays.fill(dp[rows],1); //the bottom rows, only possible way . move right\n      \n      for(int row=0;row<=rows;row++) //the righmost wall, only possible way.. move down\n        dp[row][cols]=1;\n      \n      for(int row=rows-1;row>=0;row--){\n        for(int col=cols-1;col>=0;col--){\n          dp[row][col] = dp[row+1][col] + dp[row][col+1];\n        }\n      }\n      \n      //we know for fact that all dp[i][j+1] paths are lexicographically smaller than dp[i+1][j], since \'H\' movement is lexicographically smaller than \'V\', we compare k with horizontal movement\n\t  //if moving horizontal gives more ways than k, then we move horizontal, if it gives less ways than we need for k, we move vertical and since we are skipping all ways created by moving horizontal, we decrement k by those all ways created by moving horizontal...\n      //if we reach wall, we keep moving along the wall, only possible way\n      \n      StringBuilder result = new StringBuilder();\n      \n      int positionX = 0, positionY=0;\n      \n      while(positionX!=rows || positionY!=cols){\n        \n        if(positionX==rows){\n          while(positionY!=cols){\n            result.append(\'H\');\n            positionY++;\n          }\n           return result.toString();\n        }\n        \n        if(positionY==cols){\n          while(positionX!=rows){\n            result.append(\'V\');\n            positionX++;\n          }\n          return result.toString();\n        }\n        \n        if(dp[positionX][positionY+1] >= k){\n          result.append(\'H\');\n          positionY++;\n        }else{\n           result.append(\'V\');\n           k-= dp[positionX][positionY+1]; //skipping all horizontal moving ways\n           positionX++;\n        } \n      }      \n      \n      return result.toString();\n    }\n}\n```
[]