文章目录

前期知识
- 516. 最长回文子序列
- - 思路1——转换问题：求 s 和反转后 s 的 LCS（最长公共子序列）
  - 思路2——区间DP：从两侧向内缩小问题规模
  - - 补充：记忆化搜索代码
- 1039. 多边形三角剖分的最低得分
- - 从记忆化搜索开始
  - 翻译成递推
典型例题
相关练习题目
- 375. 猜数字大小 II https://leetcode.cn/problems/guess-number-higher-or-lower-ii/
- - 记忆化搜索
  - 递推dp
- 1312. 让字符串成为回文串的最少插入次数 https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
- - 记忆化搜索
  - 区间dp
  - 解法2：转换成最长回文子序列
- 1771. 由子序列构造的最长回文串的长度 https://leetcode.cn/problems/maximize-palindrome-length-from-subsequences/
- 1547. 切棍子的最小成本 https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/
- - 记忆化搜索
  - 递推dp
- 1000. 合并石头的最低成本 https://leetcode.cn/problems/minimum-cost-to-merge-stones/ ⭐⭐⭐⭐⭐
- - 前置知识——前缀和
  - 思路：寻找子问题
  - 记忆化搜索
  - - 记忆化搜索的优化
  - DP递推

前期知识

在这里插入图片描述
通过本篇文章的学习，最重要的就是学会 记忆化搜索 的方法，
很多问题直接写递推DP 会比较困难，但是寻找子问题，按照记忆化搜索的方式会比较简单。
之后还可以相对容易地将记忆化搜索的代码翻译成递推 DP。

516. 最长回文子序列

516. 最长回文子序列
在这里插入图片描述

思路1——转换问题：求 s 和反转后 s 的 LCS（最长公共子序列）

因为回文子序列从前往后和从后往前是一样的，所以可以转换成求
s = eacbba
和
s_rev = abbace
的最长公共子序列的长度。最长公共子序列的方法参见：【算法】最长公共子序列&编辑距离

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        String s2 = new StringBuilder(s).reverse().toString();
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                } else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n][n];
    }
}

思路2——区间DP：从两侧向内缩小问题规模

在这里插入图片描述
这道题目相对简单一些，可以直接写出递推公式。

刚开始不确定 i 和 j 的枚举顺序，这时候看看状态转移方法看看它们是从哪里转移来的就好了。

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        // dp[i][j]表示从i~j的区间中，最长回文子序列的长度
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            dp[i][i] = 1;   // dp数组初始化
            for (int j = i + 1; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) {   
                    // i和j相同，可以选
                    dp[i][j] = Math.max(dp[i + 1][j - 1] + 2, dp[i][j]);
                } else {
                    // 不选i或者不选j
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);    
                }
            }
        }
        return dp[0][n - 1];
    }
}

补充：记忆化搜索代码

class Solution {
    int[][] memo;
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        this.memo = new int[n][n];
        return dfs(s.toCharArray(), 0, n - 1);
    }

    public int dfs(char[] s, int l, int r) {
        if (l > r) return 0;
        if (memo[l][r] != 0) return memo[l][r];
        if (l == r) return memo[l][r] = 1;
        if (s[l] == s[r]) memo[l][r] = Math.max(memo[l][r], dfs(s, l + 1, r - 1) + 2);
        else memo[l][r] = Math.max(dfs(s, l, r - 1), dfs(s, l + 1, r));
        return memo[l][r];
    }
}

1039. 多边形三角剖分的最低得分

1039. 多边形三角剖分的最低得分
在这里插入图片描述

把这题当成经典例题，学习记忆化搜索的写法。

从记忆化搜索开始

在这里插入图片描述

所谓记忆化搜索，就是用一个数组存一下各个 dfs 的结果，让 dfs 不会再重复计算。

class Solution {
    int[][] memo;

    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        this.memo = new int[n][n];
        return dfs(values, 0, n - 1);
    }

    public int dfs(int[] values, int l, int r) {
        if (memo[l][r] != 0) return memo[l][r];
        else if (r == l + 1) memo[l][r] = 0;
        else {
            int res = Integer.MAX_VALUE;
            for (int i = l + 1; i < r; ++i) {
                res = Math.min(res, dfs(values, i, r) + dfs(values, l, i) + values[l] * values[i] * values[r]);
            }
            memo[l][r] = res;
        }
        return memo[l][r];
    }
}

翻译成递推

在这里插入图片描述

上图中说了，分不清枚举的顺序，就看状态转移的时候是从哪里转移过来的。

class Solution {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];
        for (int i = n - 3; i >= 0; --i) {
            for (int j = i + 2; j < n; ++j) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; ++k) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

典型例题

相关练习题目

375. 猜数字大小 II https://leetcode.cn/problems/guess-number-higher-or-lower-ii/

https://leetcode.cn/problems/guess-number-higher-or-lower-ii/

在这里插入图片描述

记忆化搜索

当只有一个数字需要被选择时，消耗是 0
当有两个数字需要被选择时，消耗是大的那一个，因为要保证游戏一定胜利

res = Math.min(res, Math.max(dfs(l, i - 1), dfs(i + 1, r)) + i);

从记忆化搜索开始写，好写一些。

class Solution {
    int[][] memo;

    public int getMoneyAmount(int n) {
        memo = new int[n + 1][n + 1];
        return dfs(1, n);
    }

    public int dfs(int l, int r) {
        if (l >= r) return 0;
        if (memo[l][r] != 0) return memo[l][r];
        int res = Integer.MAX_VALUE;
        for (int i = l; i <= r; ++i) {
            res = Math.min(res, Math.max(dfs(l, i - 1), dfs(i + 1, r)) + i);
        }
        memo[l][r] = res;
        return res;
    }
}

递推dp

同样看递推的方向来判断枚举 i 和 j 的顺序。

class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 2][n + 2];
        for (int i = n; i >= 1; --i) {
            for (int j = i + 1; j <= n; ++j) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k <= j; ++k) {
                    dp[i][j] = Math.min(dp[i][j], k + Math.max(dp[i][k - 1], dp[k + 1][j]));
                }
            }
        }
        return dp[1][n];
    }
}

1312. 让字符串成为回文串的最少插入次数 https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/

https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
在这里插入图片描述

当字符串的长度为 1 时，答案是0。
否则，当 s[i] != s[j] 时，需要增添一个元素 s[i] 或者 s[j]。答案是 dfs(s, l + 1, r) 和 dfs(s, l, r - 1) 之间的最小值 + 1。
当 s[i] == s[j] 时，答案是 dfs(s, l + 1, r - 1) ，因为这两个元素不需要考虑了。

记忆化搜索

class Solution {
    int[][] memo;

    public int minInsertions(String s) {
        int n = s.length();
        this.memo = new int[n][n];
        return dfs(s, 0, n - 1);
    }

    public int dfs(String s, int l, int r) {
        if (l >= r) return 0;
        if (memo[l][r] != 0) return memo[l][r];
        
        if (s.charAt(l) == s.charAt(r)) memo[l][r] = dfs(s, l + 1, r - 1);
        else memo[l][r] = 1 + Math.min(dfs(s, l + 1, r), dfs(s, l, r - 1));
        return memo[l][r];
    }
}

dfs 中第一句写的 if (l >= r) return 0; ，其实我也不知道在 dfs 的过程中 l 会不会大于 r，但是无所谓，因为只有当 l < r 时我才想让函数接着往下走。
所以，何必写成 l == r 呢？不如宽松一点条件，省得万一 l 可能会大于 r。

区间dp

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1];
                else dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
}

解法2：转换成最长回文子序列

考虑增加后的回文字符串，对称的两个字符不可能都是新增加的，要么其中一个是新增加的，要么就是都属于原字符串。如果只把两个都属于原字符串的那些字符作为子序列提出来（奇数长度的情况包含中间那个），他是一个回文子序列，并且是原字符串的回文子序列。并且有insertion step的数量就是原字符串长度 - 回文子序列的长度（要为那些本来只有一个的字符手动增加对称的字符）。

因此，一个增加字符使得原字符串变成回文的方案，对应着一个原字符串的回文子序列。并且，回文子序列越长，需要增加的字符越少。

从而变成找原字符串的最长回文子序列的问题。

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        // dp[i][j]表示从i~j之间的最长回文子序列的长度
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
                else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return n - dp[0][n - 1];
    }
}

1771. 由子序列构造的最长回文串的长度 https://leetcode.cn/problems/maximize-palindrome-length-from-subsequences/

https://leetcode.cn/problems/maximize-palindrome-length-from-subsequences/

在这里插入图片描述
这道题目本质上就是将 s1 和 s2 合并之后，求最长回文子序列，同时要求这个最长回文子序列的首元素在 s1 中，末尾元素在 s2 中。

class Solution {
    public int longestPalindrome(String word1, String word2) {
        String s = word1 + word2;
        int n = s.length(), n1 = word1.length(), ans = 0;
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                    if (i < n1 && j >= n1) ans = Math.max(ans, dp[i][j]);   // 需要在两个字符串上都选择
                }
                else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            } 
        }
        return ans;
    }
}

1547. 切棍子的最小成本 https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/

https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/

在这里插入图片描述
示例：

记忆化搜索

通过 dfs 求从 i ~ j 之间切割的最小花费。

class Solution {
    int[][] memo;   // 记忆数组

    public int minCost(int n, int[] cuts) {
        Arrays.sort(cuts);
        this.memo = new int[cuts.length][cuts.length];
        return dfs(cuts, 0, cuts.length - 1, 0, n);
    }

    public int dfs(int[] cuts, int l, int r, int start, int end) {
        if (l > r) return 0;
        if (memo[l][r] != 0) return memo[l][r];
        int res = Integer.MAX_VALUE;
        for (int i = l; i <= r; ++i) {
            res = Math.min(res, end - start + dfs(cuts, l, i - 1, start, cuts[i]) + dfs(cuts, i + 1, r, cuts[i], end));
        }
        memo[l][r] = res;
        return res;
    }
}

递推dp

先留给读者思考了。（实际上是自己不太会改
思考不出来可以看 https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/solution/qie-gun-zi-de-zui-xiao-cheng-ben-by-leetcode-solut/

在这里插入代码片

1000. 合并石头的最低成本 https://leetcode.cn/problems/minimum-cost-to-merge-stones/ ⭐⭐⭐⭐⭐

https://leetcode.cn/problems/minimum-cost-to-merge-stones/

在这里插入图片描述

这道题目的难度还是很大的，但是学会之后收益颇丰。

前置知识——前缀和

在这里插入图片描述

思路：寻找子问题

在这里插入图片描述

Q：什么时候输出-1呢？
A：从 n 堆变成 1 堆，需要减少 n - 1 堆，而每次合并都会减少 k - 1 堆，所以 n - 1 必须是 k - 1 的倍数。

记忆化搜索

将上面的思路转换成记忆化搜索。

class Solution {
    int[][][] memo;     // 记忆数组
    int[] s;            // 前缀和数组
    int k;

    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) return -1;  // 返回-1
        this.s = new int[n + 1];
        // 计算前缀和数组
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + stones[i];
        }
        this.k = k;
        this.memo = new int[n][n][k + 1];   // 表示从i~j合并成p堆的最低成本
        return dfs(0, n - 1, 1);    // 最后返回的是从0~n-1合并成1堆的最低成本
    }

    public int dfs(int l, int r, int p) {
        if (p == 1) return memo[l][r][p] = l == r? 0: dfs(l, r, k) + s[r + 1] - s[l];
        if (memo[l][r][p] != 0) return memo[l][r][p];   // 如果已经计算过了
        int res = Integer.MAX_VALUE;
        for (int i = l; i < r; i += k - 1) {
            res = Math.min(res, dfs(l, i, 1) + dfs(i + 1, r, p - 1));
        }
        return memo[l][r][p] = res;
    }
}

动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间

时间复杂度： $O(N^3)$
空间复杂度： $O(N^2K)$

记忆化搜索的优化

在这里插入图片描述

class Solution {
    int[][] memo;     // 记忆数组
    int[] s;            // 前缀和数组
    int k;

    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) return -1;  // 返回-1
        this.s = new int[n + 1];
        // 计算前缀和数组
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + stones[i];
        }
        this.k = k;
        this.memo = new int[n][n];   // 表示从i~j合并成1堆的最低成本
        return dfs(0, n - 1);    // 最后返回的是从0~n-1合并成1堆的最低成本
    }

    public int dfs(int l, int r) {
        if (l == r) return 0;                   // 如果已经是一堆了
        if (memo[l][r] != 0) return memo[l][r];   // 如果已经计算过了
        int res = Integer.MAX_VALUE;
        for (int i = l; i < r; i += k - 1) {
            res = Math.min(res, dfs(l, i) + dfs(i + 1, r));
        }
        if ((r - l) % (k - 1) == 0) {           // 如果可以合并成一堆
            res += s[r + 1] - s[l];
        }
        return memo[l][r] = res;
    }
}

DP递推

直接写出来递推还是挺难的，但是可以从记忆化搜索的代码 1：1 翻译成递推 DP。

class Solution {
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) return -1;  // 返回-1
        // 计算前缀和数组
        int[] s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + stones[i];
        }

        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                dp[i][j] = Integer.MAX_VALUE / 2;
                for (int m = i; m < j; m += k - 1) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
                }
                if ((j - i) % (k - 1) == 0) dp[i][j] += s[j + 1] - s[i];
            }
        }
        return dp[0][n - 1];
    }
}