动态规划 - 背包问题 & 回文串分割

目录

1.背包问题

1.1 题目描述

1.2 画图分析

1.3 思路分析

1.4 代码示例

2. 回文串分割

2.1 题目描述

2.2 思路分析

2.3 代码示例

---

1.背包问题

1.1 题目描述

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小
和数组 V 表示每个物品的价值.问最多能装入背包的总价值是多大?
 
1.A[i], V[i], n, m 均为整数
2.你不能将物品进行切分
3.你所挑选的要装入背包的物品的总大小不能超过 m
4.每个物品只能取一次
5.m <= 1000
len(A),len(V)<=100

1.2 画图分析

• 第 i 个商品放入包中的价值

此时两个等式其实都可以由 F(i, j) = F(i - 1, j - a[i -1]) + v[i -1]  来代替 

•  第 i 个商品的大小 > 包的大小

此时 F(i, j) = F(i - 1, j) 

1.3 思路分析

状态 F(i, j)：从前 i 个商品中选择，包的大小为 j 时的最大价值。（商品的索引从 1 开始，数组的索引从 0 开始）

状态转移方程：

• a[i - 1]  >  j             F(i, j) = F(i - 1, j)
• a[i - 1] <= j             F(i, j) = F(i - 1, j - a[i - 1]) + v[i - 1]

初始状态：F(i, 0) = F(0, j) = 0，由于每一个商品的价值都可能和前一行的某一列有关，为了防止数组越界，我们申请一个行，列比商品数、包都大一的二维数组 array[n + 1][m + 1].

返回结果：array[n][m].

结合具体示例理解：

 

1.4 代码示例

public class Solution {
    public static int backPackII(int m, int[] a, int[] v) {
        int number = a.length;
        int[][] array = new int[number + 1][m + 1];
        // 初始状态 array[0][j] = array[i][0] = 0
        for(int i = 1; i < number + 1; i++) {
            for(int j = 1; j < m + 1; j++) {
                // 状态转移方程
                if(a[i - 1] > j) {
                    array[i][j] = array[i - 1][j];
                } else {
                    array[i][j] = Math.max(array[i -1][j], array[i - 1][j - a[i - 1]] + v[i - 1]);
                }
            }
        }
        // 返回结果
        return array[number][m];
    }
}

【优化】一维数组

上述代码可以优化为只用一个一维数组，循环还是两层，但是要注意的是：内层循环需要从后往前走，因为状态方程需要用未更新之前的值，如果从小到大更新的话，我们是先更新前面这些列的值，那么后面使用的就都是更新过的值了；但是对于二维数组，从前往后，从后往前都是可以的。

public class Solution {
    public int backPackII(int m, int[] a, int[] v) {
        int number = a.length;
        // 省去行
        int[] array = new int[m + 1];
        for(int i = 1; i < number + 1; i++) {
            // 注意从后往前更新
            for(int j = m; j > 0; j--) {
                if(a[i - 1] <= j) {
                    // 状态转移方程
                    array[j] = Math.max(array[j], array[j - a[i - 1]] + v[i - 1]);
                }
            }
        }
        return array[m];
    }
}

2. 回文串分割

2.1 题目描述

给出一个字符串s，分割s使得分割出的每一个子串都是回文串
计算将字符串s分割成回文分割结果的最小切割数
例如:给定字符串s="aab",
返回1，因为回文分割结果["aa","b"]是切割一次生成的。

示例1：

输入："aab"
返回值：1

2.2 思路分析

问题：s 的最小分割次数

状态 F(i) ：s 的前 i 个字符最小的分割次数

状态转移方程：

• [1, i] 是回文串      array[i] = 0;
• [1, i] 不是回文串，且 i < j && [j + 1, i] 是回文串        min(F(i), F(j) + 1);

初始状态：F(i) = i - 1 ，i  从 1 开始

返回结果：F(s.length())

结合具体实例理解 min(F(i), F(j) + 1)  :

 

2.3 代码示例

public class Solution {
    public boolean isPal(String s) {
        int left = 0;
        int right = s.length() - 1;
        while(left < right) {
            if(s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    public int minCut (String s) {
        if(s.length() == 0 || s.length() == 1) {
            return 0;
        }
        int[] array = new int[s.length() + 1];
        // 初始状态
        for(int i = 1; i < array.length; i++) {
            array[i] = i - 1;
        }
        for(int i = 2; i < array.length; i++) {
            // 判断整体是否为回文串
            if(isPal(s.substring(0,i))) {
                array[i] = 0;
            } else {
                for(int j = 1; j < i; j++) {
                    // j < i && [j + 1, i] 是否为回文串
                    if(isPal(s.substring(j, i))) {
                        // 状态转移方程
                        array[i] = Math.min(array[i], array[j] + 1);
                    }
                }
            }
        }
        return array[s.length()];
    }
}