从递归到记忆化搜索再到动态规划|单词拆分、最长递增子序列

从递归到记忆化搜索再到动态规划|单词拆分、最长递增子序列

根据递归判断出需要用数组保存已经计算过的内容，采用记忆化搜索方式，推算出递推公式，实现动态规划。

模板代码

递归

import javax.management.loading.MLetMBean;
import java.util.Arrays;

/**
 * $139 $300的模板代码
 */
public class Solution {
    //定义全局变量;
    int len;
    public int func() {
        //全局变量赋值;

        //递归
        process();

        //递归结果处理;
    }

    //[index, len)
    private int process(int index) {
        int res = ;
        if (index == 边界值) { //边界值处理
            res =  ;
        } else { //否则递归查询
            for (int i = index; i < len; i++) {
                //逻辑处理
                res = ;
            }
        }
        return res;
    }
}

递归/记忆化搜索，使用dp[]保存中间结果

创建dp表，每次递归前先查询表，若得到结果为-1，表示该值未计算过，否则直接从表中获取值。计算完值后将值填入表中。

import javax.management.loading.MLetMBean;
import java.util.Arrays;

/**
 * $139 $300的模板代码
 */
public class Solution {
    //定义全局变量;
    int len;
    int[] dp;
    public int func2() {
        //全局变量赋值

        //1.初始化dp[]
        Arrays.fill(dp, -1);

        //4.表处理
    }

    private int process2(int index) {
        //2.查表，-1表示未计算过
        if (dp[index] != -1) {
            return dp[index];
        }

        //3.写表
        int res = ;
        if (index == 边界值) {
            res = ;
        } else {
            for (int i = index; i < len; i++) {
                //逻辑处理
                res = ;
            }
        }
        dp[index] = res;

        return res;
    }
}

非递归/动态规划

从后往前填写表。

import javax.management.loading.MLetMBean;
import java.util.Arrays;

/**
 * $139 $300的模板代码
 */
public class Solution {
    public int func3() {
        int len;
        int[] dp;

        //1.初始化边界值
        dp[边界值] = ;

        //2.写表
        for (int i = len-1; i >= 0; i--) {
            int res = ;
            for (int j = i; j < len; j++) {
                //逻辑处理;
                res = ;
            }
            dp[i] = res;
        }

        //3.表处理
        int result = 处理后的dp[]结果;
        return result;
    }
}

139 单词拆分

OJ连接

递归

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class $139 {
    String s;
    int len;
    Set<String> set = new HashSet<>();

    int[] dp;

    //法一：递归
    public boolean wordBreak(String s, List<String> wordDict) {
        this.s = s;
        this.len = s.length();
        this.set.addAll(wordDict);

        return process(0);
    }

    //[index, len)及其子串是否在字典中
    //超过时间限制，不断递归，有一些子串被重复计算
    private boolean process(int index) {
        boolean res = false;
        if (index == len) { //index遍历完字符串，则全部与字典中的单词匹配
            res = true;
        } else { //否则递归查询
            for (int i = index; i < len; i++) {
                if (set.contains(s.substring(index, i+1))) {
                    res |= process(i+1);
                }
            }
        }
        return res;
    }
}

递归/记忆化搜索，使用dp[]保存中间结果

public class $139 {
    String s;
    int len;
    HashSet<String> set = new HashSet<>();
    int[] dp;

    //法二：递归，使用dp
    public boolean wordBreak2(String s, List<String> wordDict) {
        this.set.addAll(wordDict);
        this.s = s;
        this.len = s.length();
        this.dp = new int[this.len+1]; //+1

        //1.初始化dp
        Arrays.fill(dp, -1);

        return process2(0);
    }

    //[index, n)及其子串是否在字典中
    //使用dp[]保存已经计算过的子串结果
    private boolean process2(int index) {
        //2.查表，子串是否已计算过
        //-1表示未计算，1表示子串在字典中，0表示子串不在字典中
        if (dp[index] != -1) {
            return dp[index] == 1;
        }

        boolean res = false;
        if (index == len) { //index遍历完字符串，则全部与字典中的单词匹配
            res = true;
        } else { //否则进行计算dp[]
            for (int i = index; i < len; i++) {
                if (set.contains(s.substring(index, i+1))) {
                    res |= process2(i+1);
                }
            }
        }
        //3.写表
        dp[index] = res ? 1 : 0;

        return res;
    }
}

非递归/动态规划

public class $139 {
    String s;
    int len;
    HashSet<String> set = new HashSet<>();
    int[] dp;

    //法三：非递归，从后往前遍历
    public boolean wordBreak3(String s, List<String> wordDict) {
        int len = s.length();
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[len+1];

        //空串，默认在字典中
        dp[len] = true;

        for (int i = len-1; i >= 0; i--) {
            boolean res = false;
            for (int j = i; j < len; j++) {
                //若前缀子串[i,j]在字典中，则判断[j+1,len)及其子串是否在字典中
                if (set.contains(s.substring(i, j+1))) {
                    //[j+1,len)及其子串只要有一个在字典中，则为true
                    res |= dp[j + 1];
                }
            }
            dp[i] = res;
        }
      
        return dp[0];
    }
}

300 最长递增子序列

OJ连接

递归

import java.util.Arrays;

public class $300 {
    int[] nums;
    int len;

    //法一：递归，超出时间限制
    public int lengthOfLIS(int[] nums) {
        this.nums = nums;
        this.len = nums.length;

        //递归结果处理
        int res = 0;
        for (int i = 0; i < len; i++) {
            // System.out.print(process(i) + " ");
            res = Math.max(res, process(i));
        }
        return res;
    }

    //[index, len)递增子序列的长度
    private int process(int index) {
        int res = 1;
        if (index == len) {
            res = 1;
        } else {
            for (int i = index+1; i < len; i++) {
                if (nums[index] < nums[i]) {
                    res = Math.max(res, 1+process(i));
                    // res = 1 + process(i);
                }
            }
        }
        return res;
    }
}

递归/记忆化搜索，使用dp[]保存中间结果

import java.util.Arrays;

public class $300 {
    int[] nums;
    int len;
    int[] dp;

    //法二：递归，使用dp[]保存结果
    public int lengthOfLIS2(int[] nums) {
        this.nums = nums;
        this.len = nums.length;
        this.dp = new int[len];

        //1.初始化
        Arrays.fill(dp, -1);

        //4.表处理
        int res = 0;
        for (int i = 0; i < len; i++) {
            res = Math.max(res, process2(i));
        }
        return res;
    }

    private int process2(int index) {
        //2.查表
        if (dp[index] != -1) {
            return dp[index];
        }

        int res = 1;
        if (index == len-1) {
            res = 1;
        } else {
            for (int i = index+1; i < len; i++) {
                //若nums[i]大，则找到了一个增序列，则继续判断[i,len)上的增序列
                if (nums[index] < nums[i]) {
                    //判断增序列是否为最大值，是则更新
                    res = Math.max(res, 1+process2(i));
                }
            }
        }
        //3.写表
        dp[index] = res;

        return res;
    }
}

非递归/动态规划

import java.util.Arrays;

public class $300 {
    //法三：非递归
    public int lengthOfLIS3(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];

        //1.初始化边界值
        //最后一个数字默认是1
        dp[len-1] = 1;

        //2.写表
        for (int i = len-1; i >= 0; i--) {
            int res = 1;
            for (int j = i+1; j < len; j++) {
                //若nums[j]大，则找到了一个增序列，则继续判断[j,len)上的增序列
                if (nums[i] < nums[j]) {
                    //判断增序列是否为最大值，是则更新
                    res = Math.max(res, 1+dp[j]);
                }
            }
            dp[i] = res;
        }

        //3.表处理
        //找到dp[]的最大值
        int result = -1;
        for (int i = 0; i < len; i++) {
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}