算法问题——动态规划（公共字串）

1找到最长的公共的子序列问题具体的目标的字符串

 

2 具体的最长的上升子序列问题

 

 

1143. 最长公共子序列

 

 

/**
 * Copyright (C), 2018-2020
 * FileName: 最长公共字串
 * Author:   xjl
 * Date:     2020/8/31 18:01
 * Description:
 */
package Test_Pricate;

public class 最长公共字串 {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] t1 = text1.toCharArray();
        char[] t2 = text2.toCharArray();
        int length1 = t1.length;
        int length2 = t2.length;
        //定义一个矩阵
        int[][] dp = new int[length1 + 1][length2 + 1];
        for (int i = 1; i < length1 + 1; i++) {
            for (int j = 1; j < length2 + 1; j++) {
                //如果是的两个元素相等的话 就是去找她的的前一个元素+1
                if (t1[i - 1] == t2[j - 1]) {
                    // 这边找到一个 lcs 的元素，继续往前找
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    //谁能让 lcs 最长，就听谁的
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[length1][length2];
    }
}

300. 最长上升子序列

 

public class 最长上升子序列300 {

    public static void main(String[] args) {
        int[] array = {10, 9, 2, 5, 3, 7, 101, 18};
        int res = lengthOfLIS(array);
        System.out.println(res);
    }

    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int res = 1;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = 1;
            //从第0个位置来计算
            for (int j = 0; j < i; j++) {
                //如果是大于的话
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            //用户记录下结果的最长的数据
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

 376. 摆动序列

 

491. 递增子序列

/**
 * Copyright (C), 2018-2020
 * FileName: 递增子序列491
 * Author:   xjl
 * Date:     2020/8/31 19:33
 * Description:
 */
package Test_Pricate;

import org.junit.Test;

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

public class 递增子序列491 {
    //使用的是的dp[i]=dp[i-1]+1这个转态转移方程的
    public List findSubsequences2(int[] nums) {
        List result = new ArrayList();
        int[] dp = new int[nums.length];
        int[] index = new int[nums.length];
        //赋予初始化的值
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            index[i] = 0;
        }
        //开始记录位置
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j >= 0; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = dp[j] + 1;
                    index[i] = nums[j];
                    break;
                }
            }
        }
        //添加元素
        for (int i = 1; i < index.length; i++) {
            if (index[i] > 0 && index[i] > index[i - 1]) {
                result.add(index[i]);
            }
        }
        return result;
    }

    List temp = new ArrayList();
    List ans = new ArrayList();

    public List findSubsequences(int[] nums) {

        dfs(0, Integer.MIN_VALUE, nums);
        return ans;
    }

    //使用的是回溯的算法的来实现
    public void dfs(int cur, int last, int[] nums) {
        //如果当位置等于的最后的位置
        if (cur == nums.length) {
            if (temp.size() >= 2) {
                ans.add(new ArrayList(temp));
            }
            return;
        }
        if (nums[cur] >= last) {
            temp.add(nums[cur]);
            dfs(cur + 1, nums[cur], nums);
            temp.remove(temp.size() - 1);
        }
        if (nums[cur] != last) {
            dfs(cur + 1, last, nums);
        }
    }

    @Test
    public void test() {
        int[] array={4, 6, 7, 7};
        List subsequences = findSubsequences(array);
        for (List list:subsequences){
            for (int a:list){
                System.out.print(a+"--");
            }
            System.out.println();
        }
    }


    // 定义全局变量保存结果
    List res = new ArrayList();
    public List findSubsequences1(int[] nums) {
        // idx 初始化为 -1，开始 dfs 搜索。
        dfs(nums, -1, new ArrayList());
        return res;
    }

    private void dfs(int[] nums, int idx, List curList) {
        // 只要当前的递增序列长度大于 1，就加入到结果 res 中，然后继续搜索递增序列的下一个值。
        if (curList.size() > 1) {
            res.add(new ArrayList(curList));
        }
        // 在 [idx + 1, nums.length - 1] 范围内遍历搜索递增序列的下一个值。
        // 借助 set 对 [idx + 1, nums.length - 1] 范围内的数去重。
        Set set = new HashSet();
        for (int i = idx + 1; i < nums.length; i++) {
            // 1. 如果 set 中已经有与 nums[i] 相同的值了，说明加上 nums[i] 后的所有可能的递增序列之前已经被搜过一遍了，因此停止继续搜索。
            if (set.contains(nums[i])) {
                continue;
            }
            set.add(nums[i]);
            // 2. 如果 nums[i] >= nums[idx] 的话，说明出现了新的递增序列，因此继续 dfs 搜索（因为 curList 在这里是复用的，因此别忘了 remove 哦）
            if (idx == -1 || nums[i] >= nums[idx]) {
                curList.add(nums[i]);
                dfs(nums, i, curList);
                curList.remove(curList.size() - 1);
            }
        }
    }
}