Java 100% Faster DP | Best Explanation
Combinations[i][j] tells us how many combinations of strings/paths is possible if we start from i,j and reach destination. Number of paths/strings which can be 
Combinations[i][j] tells us how many combinations of strings/paths is possible if we start from i,j and reach destination. Number of paths/strings which can be formed at Combinations[i][j] = Combinations[i+1][j] + Combinations[i][j+1].  consider making dp for destination 2,3.\nTo start from 1,2 and reach 2,3 we will have one \'H\' and one \'V\' which is why Combinations[i][j]  will be 2(HV and VH). If we use H at first position we move right and we are left with one \'V\'.\nNow consider being on position 1,1 and same desitination.\ncombinations[i][j]= 3 because we can move right twice and down once so we have 2 \'H\' and 1 \'V\'. paths: HHV HVH VHH\nIf we choose 1st char as V and move down we will be left with HH which can make only one combination but if we go right that means curr char should be H and we are left with 1 H and 1 V which gives us 2 combinations(HV VH).\nIn conclusion if we use H as curr char we move right which give us access to strings/paths which are lexicographically smaller compared to moving down and using curr char as V.\nConsidering same destination 2,3 let k be 4 and lets start from 0,0.\nwe see that moving right means we are using 1st char as \'H\'. We compare k to strings/paths to the right(lexicographically smaller strings compared to down) combination[i][j+1]= 6 Those strings are HHHVV HHVHV HHVVH HVHHV HVHVH HVVHH combination[i+1][j]= 4 These are the strings starting from \'V\'. since k=4 is less than equal to number of strings to right It means our ans string in within them. so we move to the right. Now we are at 0,1 where num of strings is 6. On the right we have combination[i][j+1]= 3 Because these strings/paths are HVV VHV VVH and combination[i+1][j]= 3 are strings HHV HVH VHH. At position 0,0 on right we had top 6 lexicographically smallest paths and below we had 4 bigger strings and since we want 4th smallest we go right.\nNow at 0,1 we compare k with combination[i][j+1]. 4 is not less than or equal to 3 which says that 4th smallest string is not among the top 3 smallest (top 3 out of 10 and also top 3 out of top 6) which tells us that we need to move down and search for bigger top 3 string out of 1st chosen top 6 strings at 0,0. so we discard strings with rank 1,2 and 3 and choose bottom 3 which means now we will choose from 4th 5th 6th smallest strings out of original 10. But we cant keep k as 4 since we discarded 1st 2nd and 3rd smallest string and 4th smallest is actual 1st smallest from 4th 5th and 6th string that is the reason we subtract combinations[i][j+1] from k.\n```\n\tpublic String kthSmallestPath(int[] destination, int k) {\n        int rows= destination[0]+1, cols= destination[1]+1;\n        int[][] combinations= new int[rows][cols];\n        for(int i=rows-1; i>=0; i--){\n            for(int j=cols-1; j>=0; j--){\n                combinations[i][j]= (i==rows-1 || j==cols-1) ? 1 : combinations[i][j+1] + combinations[i+1][j];\n            }\n        }\n        StringBuilder sb= new StringBuilder();\n        int i=0, j=0;\n        while(i != rows-1 || j != cols-1){\n            if(i==rows-1){\n                sb.append(\'H\');\n                j++;\n            }else if(j==cols-1){\n                sb.append(\'V\');\n                i++;\n            }else if(combinations[i][j+1]>=k){\n                sb.append(\'H\');\n                j++;\n            }else{\n                sb.append(\'V\');\n                k-= combinations[i][j+1];\n                i++;\n            }\n        }\n        return String.valueOf(sb);\n    }
[]