This page explains Java solution to problem `Kth Smallest Instructions`

using `Dynamic Programming`

algorithm.

Bob is standing at cell `(0, 0)`

, and he wants to reach destination: `(row, column)`

. He can only travel right and down. You are going to help Bob by providing instructions for him to reach destination.

The instructions are represented as a string, where each character is either:

`H`

, meaning move horizontally (go right), or`V`

, meaning move vertically (go down).

Multiple instructions will lead Bob to destination. For example, if destination is `(2, 3)`

, both `HHHVV`

and `HVHVH`

are valid instructions.

However, Bob is very picky. Bob has a lucky number `k`

, and he wants the `k`

lexicographically smallest instructions that will lead him to destination. ^{th}`k`

is 1-indexed.

Given an integer array destination and an integer `k`

, return the `k`

lexicographically smallest instructions that will take Bob to destination.
^{th}

Input: destination = [2,3], k = 1Output: "HHHVV"Explanation: All the instructions that reach (2, 3) in lexicographic order are as follows:

["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].

Input: destination = [2,3], k = 2Output: "HHVHV"

```
package com.vc.hard;
class KthSmallestInstruction {
public String kthSmallestPath(int[] destination, int k) {
int rowTarget = destination[0];
int colTarget = destination[1];
int[][] matrix = new int[rowTarget + 1][colTarget + 1];
for(int row = rowTarget; row >= 0; row--) {
for(int col = colTarget; col >= 0; col--) {
if(row == rowTarget && col == colTarget) {
matrix[row][col] = 1;
}
else if(row == rowTarget) {
matrix[row][col] = matrix[row][col + 1];
}
else if(col == colTarget) {
matrix[row][col] = matrix[row + 1][col];
}
else {
matrix[row][col] = matrix[row + 1][col] + matrix[row][col + 1];
}
}
}
return helper(matrix, 0, 0, k);
}
private String helper(int[][] matrix, int row, int col, int k) {
if(row + 1 == matrix.length && col + 1 == matrix[0].length) {
return "";
}
else if(row + 1 == matrix.length) {
StringBuilder sb = new StringBuilder();
while(++col < matrix[0].length) sb.append("H");
return sb.toString();
}
else if(col + 1 == matrix[0].length) {
StringBuilder sb = new StringBuilder();
while(++row < matrix.length) sb.append("V");
return sb.toString();
}
else {
if(matrix[row][col + 1] >= k) {
return "H" + helper(matrix, row, col + 1, k);
}
else {
return "V" + helper(matrix, row + 1, col, k - matrix[row][col + 1]);
}
}
}
}
```

O(X * Y) Where

X is destination in horizontal direction

Y is destination in vertical direction

O(X * Y) Where

X is destination in horizontal direction

Y is destination in vertical direction