动态规划问题经典例题
前言
DP（Dynamic Programming）定义：
动态规划是分治思想的延伸，通俗一点来说就是大事化小，小事化无的艺术。在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。
动态规划具备了以下三个特点：
- 把原来的问题分解成了几个相似的子问题。
- 所有的子问题都只需要解决一次。
- 储存子问题的解
动态规划的本质，是对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)。
动态规划问题一般从以下四个角度考虑：
- 状态定义
- 状态间的转移方程定义
- 状态的初始化
- 返回结果
状态定义的要求：定义的状态一定要形成递推关系。
一句话概括：三特点四要素两本质
适用场景：最大值/最小值, 可不可行, 是不是，方案个数；
一、字符串分割
牛客链接
状态：
子状态：前1，2，3，…,n个字符能否根据词典中的词被成功分词
F(i): 前i个字符能否根据词典中的词被成功分词
状态递推：
F(i): true{j < i && F(j) && substr[j+1,i]能在词典中找到} OR false
在j小于i中，只要能找到一个F(j)为true，并且从j+1到i之间的字符能在词典中找到，则F(i)为true。
初始值：
对于初始值无法确定的，可以引入一个不代表实际意义的空状态，作为状态的起始；
空状态的值需要保证状态递推可以正确且顺利的进行，到底取什么值可以通过简单的例子进行验证，这里取F(0) = true；
返回结果：F(n)；
import java.util.*;
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] canBreak = new boolean[s.length() + 1];
canBreak[0] = true;
for(int i = 1;i <= s.length();i++){
for(int j = 0;j < i;j++){
if(canBreak[j] && dict.contains(s.substring(j,i))){
canBreak[i] = true;
break;
}
}
}
return canBreak[s.length()];
}
}
二、三角矩阵的最小路径和
状态：
子状态：从(n,n),(n,n-1),...(1,0),(1,1),(0,0)到最后一行的最短路径和；
F(i,j): 从(i,j)到最后一行的最短路径和；
状态递推：F(i,j) = min( F(i+1, j), F(i+1, j+1)) + triangle[i][j]；
初始值：F(n-1,0) = triangle[n-1][0], F(n-1,1) = triangle[n-1][1],..., F(n-1,n-1) = triangle[n-1][n-1]；
返回结果：F(0, 0)；
自底向上的方法，确定最后一行的最小值，然后从倒数第二行开始。
import java.util.*;
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
if(triangle.isEmpty()){
return 0;
}
//初始化
ArrayList<ArrayList<Integer>> minPathSum = new ArrayList<>(triangle);
int row = minPathSum.size();
//从倒数第二行开始
for(int i = row - 2;i >=0;i--){
for(int j = 0;j <= i;j++){
// F(i,j) = min( F(i+1, j), F(i+1, j+1)) + triangle[i][j]
int curSum = Math.min(triangle.get(i+1).get(j),triangle.get(i+1).get(j + 1)) + triangle.get(i).get(j);
minPathSum.get(i).set(j,curSum);
}
}
return minPathSum.get(0).get(0);
}
}
三、路径总数
牛客链接
状态：
子状态：从(0,0)到达(1,0),(1,1),(2,1),...(m-1,n-1)的路径数；
F(i,j): 从(0,0)到达F(i,j)的路径数
状态递推：F(i,j) = F(i-1,j) + F(i,j-1)
初始化：
特殊情况：第0行和第0列：F(0,i) = 1，F(i,0) = 1；
返回结果：F(m-1,n-1)；
import java.util.*;
public class Solution {
/**
*
* @param m int整型
* @param n int整型
* @return int整型
*/
public int uniquePaths (int m, int n) {
int[][] dp = new int[m][n];
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j++){
//处理第0行,只有一条路径
if(i == 0){
dp[i][j] = 1;
continue;
}
//处理第0列
if(j == 0){
dp[i][j] = 1;
continue;
}
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
四、最小路径和
牛客链接
状态：
子状态：从(0,0)到达(1,0),(1,1),(2,1),...(m-1,n-1)的最短路径
F(i,j): 从(0,0)到达F(i,j)的最短路径
状态递推：F(i,j) = min{F(i-1,j) , F(i,j-1)} + (i,j)；
初始化：F(0,0) = (0,0)；
特殊情况：第0行和第0列：F(0,i) = F(0,i-1) + (0,i)，F(i,0) = F(i-1,0) + (i,0)；
返回结果：F(m-1,n-1)。
import java.util.*;
public class Solution {
/**
*
* @param grid int整型二维数组
* @return int整型
*/
public int minPathSum (int[][] grid) {
if(grid == null){
return 0;
}
int row = grid.length;
int col = grid[0].length;
//从（0,0）点出发
//处理第一列
for(int i = 1;i < row;i++){
grid[i][0] = grid[i - 1][0] + grid[i][0];
}
//处理第一行
for(int j = 1;j < col;j++){
grid[0][j] = grid[0][j - 1] + grid[0][j];
}
for(int i = 1;i < row;i++){
for(int j = 1;j < col;j++){
grid[i][j] = Math.min(grid[i - 1][j],grid[i][j - 1])+grid[i][j];
}
}
return grid[row - 1][col - 1];
}
}
五、背包问题
背包问题
关于背包问题详解
描述：
有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.
问最多能装入背包的总价值是多大?
状态：F(i, j): 前i个物品放入大小为j的背包中所获得的最大价值；
状态递推：对于第i个商品，有一种例外，装不下，两种选择，放或者不放，
如果装不下：此时的价值与前i-1个的价值是一样的：F(i,j) = F(i-1,j)；
如果可以装入：需要在两种选择中找最大的：F(i, j) = max{F(i-1,j), F(i-1, j - A[i]) + V[i]}
F(i-1,j): 表示不把第i个物品放入背包中， 所以它的价值就是前i-1个物品放入大小为j的背包的最大价值
F(i-1, j - A[i]) + V[i]：表示把第i个物品放入背包中，价值增加V[i],但是需要腾出j - A[i]的大小放第i个商品；
初始化：第0行和第0列都为0，表示没有装物品时的价值都为0：F(0,j) = F(i,0) = 0；
返回值：F(n,m)；
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @param V: Given n items with value V[i]
* @return: The maximum value
*/
public int backPackII(int m, int[] A, int[] V) {
int num = A.length;
if(m == 0 || num == 0)
return 0;
//多加一行一列，用于设置初始条件
int[][] maxValue = new int[num + 1][m + 1];
//初始化所有位置为0，第一行和第一列都为0，初始条件
for(int i = 0; i <= num; ++i){
maxValue[i][0] = 0;
}
for(int i = 1; i <= m; ++i){
maxValue[0][i] = 0;
}
for(int i = 1; i <= num; ++i){
for(int j = 1; j <= m; ++j){
//第i个商品在A中对应的索引为i-1: i从1开始
//如果第i个商品大于j,说明放不下， 所以(i,j)的最大价值和(i-1,j)相同
if(A[i - 1] > j){
maxValue[i][j] = maxValue[i - 1][j]
}
else{
//如果可以装下，分两种情况，装或者不装
//如果不装，则即为(i-1, j)
//如果装，需要腾出放第i个物品大小的空间： j - A[i-1],装入之后的最大价值即为(i -1, j - A[i-1]) + 第i个商品的价值V[i - 1]
//最后在装与不装中选出最大的价值
int newValue = maxValue[i - 1][j - A[i - 1]]+ V[i - 1];
maxValue[i][j] = Math.max(newValue, maxValue[i - 1][j]);
}
}
}
//返回装入前N个商品，物品大小为m的最大价值
return maxValue[num][m];
}
}
六、 回文串分割
牛客链接
状态：
子状态：到第1,2,3,...,n个字符需要的最小分割数
F(i): 到第i个字符需要的最小分割数
状态递推：F(i) = min{F(i), 1 + F(j)}, 这里j<i && j+1到i是回文串
上式表示如果从j+1到i判断为回文字符串，且已经知道从第1个字符到第j个字符的最小切割数，那么只需要再切一次，就可以保证1-->j, j+1-->i都为回文串。
初始化：F(i) = i - 1，表示到第i个字符需要的最大分割数。
比如单个字符只需要切0次，因为单子符都为回文串，2个字符最大需要1次，3个2次…；
返回结果：F(n)；
import java.util.*;
public class Solution {
/**
*
* @param s string字符串
* @return int整型
*/
public boolean bol(String s,int start,int end){
while(start < end){
if(s.charAt(start) != s.charAt(end)){
return false;
}
start++;
end--;
}
return true;
}
public int minCut (String s) {
int m = s.length();
if(m == 0){
return 0;
}
int[] minCut = new int[m + 1];
//初始化每个字符的最大分割次数，字符从下标为1开始
// F(0）= -1，必要项，如果没有这一项，对于重叠字符串“aaaaa”会产生错误的结果
for(int i = 0;i <= m;i++){
minCut[i] = i-1;
}
//从下标为1处开始
for(int i = 1;i <= m;i++){
for(int j = 0;j < i;j++){
// 从最长串判断，如果从第j+1到i为回文字符串
// 则再加一次分割，从1到j，j+1到i的字符就全部分成了回文字符串
if(bol(s,j,i - 1)){
minCut[i] = Math.min(minCut[i],minCut[j] + 1);
}
}
}
return minCut[m];
}
}
上述方法两次循环时间复杂度是O(n^2),判断回文串时间复杂度是O(n),所以总时间复杂度为O(n^3)。对于过长的字符串，在OJ的时候会出现TLE(Time Limit Exceeded)。
优化方法：
状态：
子状态：从第一个字符到第二个字符是不是回文串，第1-3，第2-5，…
F(i,j): 字符区间 [i,j] 是否为回文串
状态递推：F(i,j): true->{s[i]==s[j] && F(i+1,j-1)} OR false
上式表示如果字符区间首尾字符相同且在去掉区间首尾字符后字符区间仍为回文串，则原字符区间为回文串。
从递推公式中可以看到第i处需要用到第i+1处的信息，所以i应该从字符串末尾遍历
初始化：F(i,j) = false
返回结果：矩阵F(n,n), 只更新一半值（i <= j），n^2 / 2。
public boolean[][] getMat(String s){
int len = s.length();
boolean[][] Mat = new boolean[len][len];
for(int i = len - 1; i >= 0; --i){
for(int j = i; j < len; ++j){
if(j == i)
// 单字符为回文字符串
Mat[i][j] = true;
else if(j == i + 1){
// 相邻字符如果相同，则为回文字符串
if(s.charAt(i) == s.charAt(j))
Mat[i][j] = true;
else
Mat[i][j] = false;
}
else{
// F(i,j) = {s[i]==s[j] && F(i+1,j-1)
// j > i+1
Mat[i][j] = (s.charAt(i) == s.charAt(j)) && Mat[i + 1][j - 1];
}
}
}
return Mat;
}
public int minCut (String s) {
int m = s.length();
if(m == 0){
return 0;
}
boolean[][] Mat = getMat(s);
int[] minCut = new int[m + 1];
//初始化每个字符的最大分割次数，字符从下标为1开始
for(int i = 0;i <= m;i++){
minCut[i] = i-1;
}
//从下标为1处开始
for(int i = 1;i <= m;i++){
for(int j = 0;j < i;j++){
if(Mat[j][i - 1]){
minCut[i] = Math.min(minCut[i],minCut[j] + 1);
}
}
}
return minCut[m];
}
}
七、编辑距离
牛客链接
状态：
子状态：word1的前1，2，3，…m个字符转换成word2的前1，2，3，…n个字符需要的编辑距离
F(i,j):word1的前i个字符于word2的前j个字符的编辑距离
状态递推：F(i,j) = min { F(i-1,j）+1, F(i,j-1) +1, F(i-1,j-1) +(w1[i]==w2[j]?0:1) }
上式表示从删除，增加和替换操作中选择一个最小操作数
F(i-1,j): w1[1,...,i-1]于w2[1,...,j]的编辑距离，删除w1[i]的字符—>F(i,j)
F(i,j-1): w1[1,...,i]于w2[1,...,j-1]的编辑距离，增加一个字符—>F(i,j)
F(i-1,j-1): w1[1,...,i-1]于w2[1,...,j-1]的编辑距离，如果w1[i]与w2[j]相同，不做任何操作，编辑距离不变，如果w1[i]与w2[j]不同，替换w1[i]的字符为w2[j]—>F(i,j)
初始化：初始化一定要是确定的值，如果这里不加入空串，初始值无法确定
F(i,0) = i :word与空串的编辑距离，删除操作；
F(0,i) = i :空串与word的编辑距离，增加操作；
返回结果：F(m,n)
import java.util.*;
public class Solution {
/**
*
* @param word1 string字符串
* @param word2 string字符串
* @return int整型
*/
public int minDistance (String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
if(word1 == null || word2 == null){
return Math.min(len1,len2);
}
int[][] minDis = new int[len1 + 1][len2 + 1];
//初始化第0列 插入操作
for(int i = 0;i <= len1;i++){
minDis[i][0] = i;
}
//初始化第0行 删除操作
for(int i = 0;i <= len2;i++){
minDis[0][i] = i;
}
for(int i = 1;i <= len1;i++){
for(int j = 1;j <= len2;j++){
minDis[i][j] = 1 + Math.min(minDis[i - 1][j],minDis[i][j - 1]);
// 判断word1的第i个字符是否与word2的第j个字符相等
if(word1.charAt(i - 1) == word2.charAt(j - 1)){
minDis[i][j] = Math.min(minDis[i - 1][j - 1],minDis[i][j]);
}else{
// 字符不相等，F(i-1,j-1)编辑距离 + 1
minDis[i][j] = Math.min(minDis[i - 1][j - 1] + 1,minDis[i][j]);
}
}
}
return minDis[len1][len2];
}
}
八、不同的子序列
牛客链接
问题翻译：S有多少个不同的子串与T相同
S[1:m]中的子串与T[1:n]相同的个数
由S的前m个字符组成的子串与T的前n个字符相同的个数
状态：
子状态：由S的前1,2,…,m个字符组成的子串与T的前1,2,…,n个字符相同的个数；
F(i,j): S[1:i]中的子串与T[1:j]相同的个数；
状态递推：在F(i,j)处需要考虑S[i] = T[j] 和 S[i] != T[j]两种情况
当S[i] = T[j]:
1: 让S[i]匹配T[j]，则F(i,j) = F(i-1,j-1)；
2: 让S[i]不匹配T[j],则问题就变为S[1:i-1]中的子串与T[1:j]相同的个数，则F(i,j) = F(i-1,j)；
故，S[i] = T[j]时，F(i,j) = F(i-1,j-1) + F(i-1,j)
当S[i] != T[j]:问题退化为S[1:i-1]中的子串与T[1:j]相同的个数，则S[i] != T[j]时，F(i,j) = F(i-1,j)；
初始化：引入空串进行初始化
F(i,0) = 1 —> S的子串与空串相同的个数，只有空串与空串相同
返回结果：F(m,n)。
import java.util.*;
public class Solution {
/**
*
* @param S string字符串
* @param T string字符串
* @return int整型
*/
public int numDistinct (String S, String T) {
if(S == null || T == null){
return 0;
}
int slen = S.length();
int tlen = T.length();
int[][] minDis = new int[slen + 1][tlen + 1];
minDis[0][0] = 1;
for(int i = 1;i <= tlen;i++){
minDis[0][i] = 0;
}
for(int i = 1;i <= slen;i++){
minDis[i][0] = 1;
}
for(int i = 1;i <= slen;i++){
for(int j = 1;j <= tlen;j++){
// S的第i个字符与T的第j个字符相同
if(S.charAt(i - 1) == T.charAt(j - 1)){
minDis[i][j] = minDis[i - 1][j] + minDis[i - 1][j - 1];
}else{
minDis[i][j] = minDis[i - 1][j];
}
}
}
return minDis[slen][tlen];
}
}