动态规划(Dynamic Programming)模式(3. 划分型)

90 阅读 0 评论 60 点赞

我是靠谱客的博主时尚汽车，最近开发中收集的这篇文章主要介绍动态规划(Dynamic Programming)模式(3. 划分型)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

划分型的动态规划，给定长度为N的序列或字符串，要求划分成若干段。

段数不限，或指定K段
每一段满足一定的性质

做法：

类似于序列型动态规划，但是通常要加上段数信息；
一般用dp[i][j]记录前i个元素，分成J段的性质，如最小代价

https://leetcode.com/problems/perfect-squares/

还是从最后一步思考：

得到的状态转移方程如下：

代码如下：

public int numSquares(int n) {
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
}

https://leetcode.com/problems/palindrome-partitioning-ii/

状态转移方程如下：

那么，如何判断S[J…I-1] 是palidrome字串？我们可以采用扩展的方式。回文串分为两种，奇数长度和偶数长度。如果是奇数长度，则可以从中心的字符往两边扩展。偶数则从中间的分隔区间往左右两侧扩展。

最终的代码如下：

public int minCut(String s) {
        int n = s.length();
        
        int[] dp = new int[n + 1];  // dp[i]表示从0 ~ i-1 的元素最小划分为dp[i]刀
        dp[0] = 0;
        
        boolean[][] isPalin = calcPalin(s.toCharArray());
        
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (isPalin[j][i - 1]) {
                    dp[i] = Math.min(dp[j] + 1, dp[i]);    
                }    
            }
        }
        return dp[n] - 1;  // 切多少刀，等于分成的份数 - 1
    }
    
    // 计算一个字符串数组中从第i个字符到第j个字符是否为回文
    private boolean[][] calcPalin(char[] s) {
        int n = s.length;
        boolean[][] res = new boolean[n][n];
        int i, j, c; // c为对称中心
        
        // odd，从每个元素开始(寻找以该元素对称的回文)
        for (c = 0; c < n; c++) {
            i = j = c;
            while (i >= 0 && j < n && s[i] == s[j]) {
                res[i][j] = true;
                i--;
                j++;
            }
        }
        
        // even，对称轴为元素间隔
        for (c = 1; c < n; c++) {
            i = c - 1;
            j = c;
            while (i >= 0 && j < n && s[i] == s[j]) {
                res[i][j] = true;
                i--;
                j++;
            }
        }
        return res;
    }

总结