动态规划 - 字符串分割(Word Break) + 三角矩阵(Triangle)
1.字符串分割(Word Break)
1.1 题目描述
给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，
使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。
例如:
给定s=“nowcode”；
dict=["now", "code"].
返回true，因为"nowcode"可以被分割成"now code".1.2 思路分析
🍁动态规划：分治思想的延伸，简单来说就是大事化小，小事化了。在将大问题化解为小问题的过程中，保存这些小问题的结果(有时也可以不保存，看场景来定)，供后面使用。
🍁动态规划具备了以下三个特点
- 把原来的问题分解成了几个相似的子问题。
- 所有的子问题都只需要解决一次。
- 储存子问题的解。
🍁动态规划问题一般从以下四个角度考虑
- 状态定义
- 状态间的转移方程定义
- 状态的初始化
- 返回结果
问题：字符串s 是否可以被分割 --> 抽象状态
状态 F(i)：字符串前 i 个字符是否可以被分割
状态转移方程：F(i) = j < i && F(j) && [j + 1, i] 是否可以在词典中找到。
初始状态：F(0) ，它相当于一个辅助状态，不能为 false，因为要满足两边都能拆分，如果 F(0) 为 false 了，那么就说明整体都不能被分割了，所以此处初始状态 F(0) 必须为 true。
返回结果：F(字符串长度) --> F(s.length())
1.3 代码示例
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] canBreak = new boolean[s.length() + 1];
// 初始状态
canBreak[0] = true;
// F(i)
for(int i = 1; i <= s.length(); i++) {
// F(0) ~ F(i - 1)
for(int j = 0; j < i; j++) {
if(canBreak[j] && dict.contains(s.substring(j,i))) {
// 每个 F(i),只要找到一种可以被分割的情况，就存储 true
canBreak[i] = true;
break;
}
}
}
// 返回最后一个状态
return canBreak[s.length()];
}
}2.三角矩阵(Triangle)
2.1 题目描述
给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，
例如，给出的三角形如下：
[[20],[30,40],[60,50,70],[40,10,80,30]]
最小的从顶部到底部的路径和是20 + 30 + 50 + 10 = 110。
注意：
如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数。2.2 思路1 - 自顶而下
问题：从顶部到底部的最小路径和
状态 F(i,j) ：从（0，0）到（i，j）的最小路径和
状态转移方程：
- 0 < j < i F(i, j) = min(F(i - 1, j) , F(i - 1, j - 1)) + array[i][j] -- > F(i, j) 的最短路径等于它上面的两条路径中的最短一条 + F(i， j) 本身的权重。
- j == 0 F(i, 0) = F(i - 1, 0) + array[i][0]
- j == i F(i, j) = F(i - 1, j - 1) + array[i][j]
初始状态：F(0, 0) = array[0][0]
返回结果：min(F(size - 1, j))，取最后一行的最小值
代码示例
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
// 处理二维数组为空的情况
if(triangle.size() == 0 || triangle.isEmpty()) {
return 0;
}
int size = triangle.size();
// 三角矩阵从上往下走，最短的路径存在了 triangle.get(size - 1).get(j) 对应的数组 array[size - 1][j] 中
int[][] array = new int[size][size];
// 先将最顶部的路径存储起来，后面的路径是通过计算前面的最短路径得到的
array[0][0] = triangle.get(0).get(0);
for(int i = 1; i < size; ++i) {
for(int j = 0; j <= i; ++j) {
// 三角形最左边的那条斜边
if(j == 0) {
array[i][j] = (array[i - 1][0] + triangle.get(i).get(j));
// 三角形最右边的斜边
} else if(j == i) {
array[i][j] = (array[i - 1][j - 1] + triangle.get(i).get(j));
// 0 < j < i
} else {
array[i][j] = (Math.min(array[i - 1][j],array[i - 1][j - 1])
+ triangle.get(i).get(j));
}
}
}
// 代码走到这里，最短路径，就存储在了数组最后一行中
int minPath = array[size - 1][0];
for(int j = 1; j < size; j++) {
// 遍历最后一行找最小值
minPath = Math.min(minPath,array[size - 1][j]);
}
return minPath;
}
}2.3 思路2 - 自底而上
状态 F(i, j)：从 F(i, j) 到达最后一行的最小路径和
状态转移方程：F(i, j)：min( F(i + 1, j), F(i + 1, j + 1) ) + array[i][j] (适用于每个点)
初始状态：F(size - 1, j) = array[size - 1][j]
返回结果：F(0, 0) = array[0][0]
代码示例
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
if(triangle.size() == 0) {
return 0;
}
int size = triangle.size();
// 先保存最后一行的值
int[][] array = new int[size][size];
for(int j = 0; j < size; j++) {
array[size - 1][j] = triangle.get(size - 1).get(j);
}
// 自底而上
for(int i = size - 2; i >= 0; i--) {
for(int j = 0; j <= i; j++) {
// F(i,j) 等于下面的路径的最小值 + F(i,j)本身的权重
array[i][j] = (Math.min(array[i + 1][j + 1], array[i + 1][j]) + triangle.get(i).get(j));
}
}
// 最短路径保存在 array[0][0] 中
return array[0][0];
}
}这两种解法都是可以的，但是自底而上这种做法相对来说更为简单，一个状态方程就适用每个点，不需要分情况讨论，也不需要最后寻找最小值。
【总结】
遇到关于矩阵，网格，字符串间的比较，匹配的问题， 单序列(一维)动规解决不了的情况下，就需要考虑双序列(二维)动规
谢谢观看！！