Link: https://leetcode.com/problems/decremental-string-concatenation/description/
## 思路
三维dp
dp[i][j][k]表示把i后面包含i的所有word逐个加在 以j开头 以k结尾的string上得到的string的最短的长度
python里面用了```@lru_cache(None)```就会自动把dp array存下来
#### 优化
参考[这里](https://leetcode.com/problems/decremental-string-concatenation/solutions/3677609/dp/)
由于我们知道每个dfs在运算的时候 拿到的start和end肯定有一个来自上一个字符串
因此我们只需要记录另一个字符是什么 以及他在start还是end即可
## Code
Python $O(26*26n)$

class Solution:
    def minimizeConcatenatedLength(self, words: List[str]) -> int:
        @lru_cache(None)
        def dfs(idx, start, end):
            if idx>=len(words): return 0
            addToBack = dfs(idx+1, start, ord(words[idx][-1])-ord('a'))
            if (ord(words[idx][0])-ord('a'))==end: addToBack -= 1

            addToFront = dfs(idx+1, ord(words[idx][0])-ord('a'), end)
            if (ord(words[idx][-1])-ord('a'))==start: addToFront -= 1

            return min(addToBack, addToFront)+len(words[idx])

        return len(words[0])+dfs(1, ord(words[0][0])-ord('a'), ord(words[0][-1])-ord('a'))

Java $O(26*26n)$

class Solution {
    public int minimizeConcatenatedLength(String[] words) {
        int[][][] dp = new int[1001][26][26];
        return words[0].length()+dfs(1, words[0].charAt(0)-'a', words[0].charAt(words[0].length()-1)-'a', words, dp);
    }
    public int dfs(int idx, int start, int end, String[] words, int[][][] dp){
        if (idx>=words.length) return 0;
        if (dp[idx][start][end]==0){
            int n = words[idx].length();
            int addToBack = dfs(idx+1, start, words[idx].charAt(n-1)-'a', words, dp);
            if((words[idx].charAt(0)-'a')==end) addToBack -= 1;

            int addToFront = dfs(idx+1, words[idx].charAt(0)-'a', end, words, dp);
            if((words[idx].charAt(n-1)-'a')==start) addToFront -= 1;

            dp[idx][start][end] = Math.min(addToBack, addToFront)+words[idx].length();
        }
        return dp[idx][start][end];
    }
}

Java $O(26*2*n)$

class Solution {
    public int minimizeConcatenatedLength(String[] words) {
        int[][][] dp = new int[1001][26][2];
        return words[0].length()+dfs(1, words[0].charAt(0)-'a', true, words, dp);
    }
    public int dfs(int idx, int ch, boolean left, String[] words, int[][][] dp){
        if (idx>=words.length) return 0;
        if (dp[idx][ch][left?1:0]==0){
            int n = words[idx].length();
            int start = left ? ch : (words[idx-1].charAt(0)-'a');
            int end = !left ? ch : (words[idx-1].charAt(words[idx-1].length()-1)-'a');

            int addToBack = dfs(idx+1, start, true, words, dp);
            if((words[idx].charAt(0)-'a')==end) addToBack -= 1;

            int addToFront = dfs(idx+1, end, false, words, dp);
            if((words[idx].charAt(n-1)-'a')==start) addToFront -= 1;

            dp[idx][ch][left?1:0] = Math.min(addToBack, addToFront)+words[idx].length();
        }
        return dp[idx][ch][left?1:0];
    }
}