一、目的

1. 了解动态规划法思想；
2. 掌握动态规划算法步骤；
3. 学会使用动态规划算法实现矩阵连乘。

二、内容

1.矩阵连乘

给定n个矩阵：A1,A2,…,An，其中Ai与Ai+1是可乘的，i=1，2…，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。 输入：矩阵个数 如，3 依次输入矩阵的行数和最后一个矩阵的列数 如10 5 15 10 输出：最小计算量的值

2.单词划分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

1、拆分时可以重复使用字典中的单词。 2、你可以假设字典中没有重复的单词。

示例 ：

输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

三、解体思路及步骤

Q1：给定n个矩阵：A1,A2,…,An，其中Ai与Ai+1是可乘的，i=1，2…，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。 输入：矩阵个数 如，3 依次输入矩阵的行数和最后一个矩阵的列数 如10 5 15 10 输出：最小计算量的值

package day04;
import java.util.*;
public class test01 {
    static int N=100;
    static int []p=new int[N];
    static int [][]m=new int[N][N];
    static int [][]s=new int[N][N];
    static int n;
    static void matrixchain(){
        int i,j,r,k;
        for( i=0;i<N;i++){
            for (j=0;j<N;j++){
                if(i==j){
                    m[i][j]=0;
                    s[i][j]=0;
                }
            }
        }
        for(r=2;r<=n;r++){
            for(i=1;i<=n-r+1;i++){
                j=i+r-1;
                m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
                s[i][j]=i;
                for(k=i+1;k<j;k++){
                    int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    if(t<m[i][j])
                    {
                        m[i][j]=t;
                        s[i][j]=k;
                    }
                }
            }
        }
    }
    static void print(int i,int j){
        if(i==j){
            System.out.print("A["+i+"]");
            return;
        }
        System.out.print("(");
        print(i,s[i][j]);
        print(s[i][j]+1,j);
        System.out.print(")");
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入矩阵的个数n个数：");
        n=sc.nextInt();
        int i,j;
        System.out.println("请一次输入每个矩阵的行数和最后一个矩阵的列数：");
        for (i=0;i<=n;i++){
            p[i]=sc.nextInt();
        }
        matrixchain();
        print(1,n);
        System.out.println();
        System.out.println("最小计算量的值为："+m[1][n]);
    }
}

Q2：给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

分析

1. 创建一个布尔数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符是否可以用词典中的单词拼接出来。并初始化 dp 数组，dp[0] 设置为 true，因为一个空字符串可以看作是一个长度为 0 的单词。

2. 然后遍历字符串 s，从索引 i = 1 开始，对于每个索引 i，尝试将 s 的第 i 个字符到整个字符串作为一个新的单词，然后检查剩下的 (i - 1) 个字符组成的子串是否已经在词典 wordDict 中，如果在就设置 dp[i] 为 true，否则 dp[i] 保持 false。

3. 最终，返回 dp[s.length()]，即表示整个字符串 s 是否能通过字典中的单词组成。

4. package day04;
   import java.util.*;
   
   public class test02 {
       public boolean wordBreak(String s, List<String> wordDict) {
           boolean[] dp = new boolean[s.length() + 1];
           dp[0] = true;
           Set<String> wordSet = new HashSet<>(wordDict);
           for (int i = 1; i <= s.length(); i++) {
               for (int j = 0; j < i; j++) {
                   String word = s.substring(j, i);
                   if (wordSet.contains(word) && dp[j]) {
                       dp[i] = true;
                       break;
                   }
               }
           }
           return dp[s.length()];
       }
   
       public static void main(String[] args) {
           test02 wordBreak = new test02();
           List<String> wordDict = Arrays.asList("apple", "pen", "applepen", "pine", "pineapple");
           String s = "applepenapple";
           System.out.println(wordBreak.wordBreak(s, wordDict));
           s = "pineapple";
           System.out.println(wordBreak.wordBreak(s, wordDict));
           s = "applepen";
           System.out.println(wordBreak.wordBreak(s, wordDict));
           s = "pine";
           System.out.println(wordBreak.wordBreak(s, wordDict));
           s = "apple pine";
           System.out.println(wordBreak.wordBreak(s, wordDict));
           wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");
           s = "catsanddog";
           System.out.println(wordBreak.wordBreak(s, wordDict));
       }
   }