动态规划-Minimum Distance to Type a Word Using Two Fingers

2020-01-12 18:28:13

问题描述：

问题求解：

本题还是非常困难的，至少我在看到这个题目的时候是没有想到怎么解决的。我当时联想到的题目是那条grid走两遍的题目，那条题目也很麻烦，使用的是dp。

本题最难的地方在于如何定义状态，其实本题可以看作是个路径规划问题，所以状态就是左指在的位置和右指在位置以及当前的字符位置。

之后递归去遍历解空间即可。

    int[][][] dp = new int[27][27][301];

    public int minimumDistance(String word) {

        return dfs(word, 0, 0, 0);

    }

    private int dfs(String word, int start, int l, int r) {

        if (start >= word.length()) return 0;

        if (dp[l][r][start] != 0) return dp[l][r][start];

        int idx = word.charAt(start) - 'A' + 1;

        dp[l][r][start] = Math.min(dist(l, idx) + dfs(word, start + 1, idx, r), dist(r, idx) + dfs(word, start + 1, l, idx));

        return dp[l][r][start];

    }

    private int dist(int from, int to) {

        if (from == 0) return 0;

        int x1 = (from - 1) / 6;

        int y1 = (from - 1) % 6;

        int x2 = (to - 1) / 6;

        int y2 = (to - 1) % 6;

        return Math.abs(x1 - x2) + Math.abs(y1 - y2);

    }

巴特西

动态规划-Minimum Distance to Type a Word Using Two Fingers

最新文章

热门文章