动态规划 - 字符串分割(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 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> 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> 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];
    }
}

这两种解法都是可以的，但是自底而上这种做法相对来说更为简单，一个状态方程就适用每个点，不需要分情况讨论，也不需要最后寻找最小值。

【总结】

遇到关于矩阵，网格，字符串间的比较，匹配的问题， 单序列(一维)动规解决不了的情况下，就需要考虑双序列(二维)动规