[Java] Bottom up dp O(m*n) solution
just need to pre calculate the combination in the dp array. then at every step, choose to go right if the rest of matrix with i rows, j - 1 columns has more pat
just need to pre calculate the combination in the dp array. then at every step, choose to go right if the rest of matrix with i rows, j - 1 columns has more paths than k. choose to go down otherwise. \n\n```\npublic String kthSmallestPath(int[] destination, int k) {\n    // dp(i, j) means how many paths are there for matrix of size i row and j column.\n\tint[][] dp = new int[destination[0] + 1][destination[1] + 1];\n\tfor(int i = 0; i <= destination[0]; i++){\n\t\tfor(int j = 0; j <= destination[1]; j++) {\n\t\t\tif(i == 0 && j == 0) dp[i][j] = 1;\n\t\t\telse if(i == 0) dp[i][j] = dp[i][j - 1];\n\t\t\telse if(j == 0) dp[i][j] = dp[i - 1][j];\n\t\t\telse dp[i][j] = dp[i][j - 1] + dp[i - 1][j];\n\t\t}\n\t}\n\tStringBuilder sb = new StringBuilder();\n\tint i = destination[0], j = destination[1];\n\twhile(i != 0 && j != 0) {\n\t    // if k is smaller than or equal with the number of paths starting with H, then we pick \'H\' for current position.\n\t\tif(dp[i][j - 1] >= k) {\n\t\t\tj--;\n\t\t\tsb.append(\'H\');\n\t\t// if k is larger than the number of paths starting with \'H\', we have to pick V then.\n\t\t}else {\n\t\t\tk -= dp[i][j - 1];\n\t\t\ti--;\n\t\t\tsb.append(\'V\');\n\t\t}\n\t}\n\tfor(int m = 0; m < i; m++) sb.append(\'V\');\n\tfor(int m = 0; m < j; m++) sb.append(\'H\');\n\treturn sb.toString();\n}\n```
[]