动态规划设计

1. 最长子序列问题

最长上升不连续子序列

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

// 最长上升不连续子序列,可以使用dp[j],来表示前j个数的最长上升子序列,那么需要维护一个max来统计最大值
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for(int i=1;i<nums.length;i++){
            int curMax = 0;
            for(int j=0;j<i;j++){
                if(nums[i] > nums[j]){
                    curMax = Math.max(curMax,dp[j]);
                }
            }
            dp[i] = curMax + 1;
            max = Math.max(dp[i],max);
        }
        return max;
    }

// 当然更快速的方法是使用二分查找进行插入

递增子序列

给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。

示例:

输入: [4, 6, 7, 7] 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

这里采用组合回溯的方法:

组合回溯模板主要用于生成非全排列的子集,同时可以用来尝试数值

组合回溯的模板

// 这里使用preIndex可以避免已经选过的,再次给当前位置赋值
// 每一次回溯实际是给当前位置curPos 进行赋值操作
public void backTrack(int[] nums,int curPos,int preIndex){
    // 递归出口
    if(curPos == k){
        // 本题没有在这里return主要是由于,生成所有子集
        return;
    }
    // 这里实际类似于给当前位置赋值
    //backTrack(nums[curPos]=x1,curPos+1....)
    //backTrack(nums[curPos]=x2,curPos+1....)
    //backTrack(nums[curPos]=x3,curPos+1....)
    for(int i=preIndex+1;i<nums.length;i++){
        // 这里可以添加各种判断 
        // hashSet保证 当前位置不赋值相同的数,避免结果出现相同值,nums[curPos] = x;
        backTrack(nums,curPos+1,i);
        // 数组不需要回溯,直接赋值覆盖即可
    }
}
 List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        // 枚举
        if(nums == null || nums.length == 0){
            return res;
        }
        backTrack(nums,new int[nums.length],0,-1,Integer.MIN_VALUE);
        return res;
    }

    public void backTrack(int[] nums,int[] tmp,int curPos,int preIndex,int pre){
        if(curPos >1){
            List<Integer> list = new ArrayList<>();
            for(int i=0;i<curPos;i++){
                list.add(tmp[i]);
            }
            res.add(list);
        }

        HashSet<Integer> set = new HashSet<>();
        for(int i=preIndex+1;i<nums.length;i++){
            if(!set.contains(nums[i]) && pre <= nums[i]){
                tmp[curPos] = nums[i];
                set.add(nums[i]);
                backTrack(nums,tmp,curPos+1,i,nums[i]);
            }
        }
    }

最长递增子序列的个数

给定一个未排序的整数数组,找到最长递增子序列的个数。

示例 1:

输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。 示例 2:

输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5

求最大长度的个数,实际是基于最大长度算法 进行更新

dp[i] 代表 dp[i] 以i结尾的子序列的最大长度,因为这里需要统计 最大长度的个数,思路是 某一个位置j num[j] < num[i] 的情况下, dp[j] > dp[i] , dp[i] 的 最大长度是dp[j] + 1, 那么他的最大个数是 count[i] += count[j] , 例如

1234 7 1235 7

 // 思路,使用length 数组,记录,当前位置的最大长度,count[i] 统计当前位置最大长度的次数
    public int findNumberOfLIS(int[] nums) {
        if(nums == null || nums.length <= 1 ){
            return nums.length;
        }

        int[] count = new int[nums.length];
        int[] length = new int[nums.length];
        Arrays.fill(count,1);
        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[i] > nums[j]){
                    if(length[j] >= length[i]){
                        length[i] = length[j] + 1;
                        count[i] = count[j];
                    }else if(length[j] + 1 == length[i]){
                        count[i] += count[j];
                    }
                }
            }
        }
        // 找到最长位置的index,返回最长位置数量
        int maxLength = 0;
        for(int i=0;i<nums.length;i++){
            if(maxLength < length[i]){
                maxLength = length[i];
            }
        }
        int ans = 0;
        for(int i=0;i<nums.length;i++){
            if(maxLength == length[i]){
                ans += count[i];
            }
        }
        return ans;
    }

2.背包问题

背包问题就是选与不选的问题,问 容量w 和 物品 n 下选择最多价值,就先求1,1 ,12 ,等情况,反向递推

  public int packet(int n, int k, int[] w,int[] v){
        int[][] dp = new int[n+1][k+1];
        for(int i=1;i<=n;i++){
            for (int j=1;j<=k;j++){
                if(j > w[i]){
                    dp[i][j] = Math.max(dp[i-1][j-w[i]] + v[i],dp[i-1][j]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][k];
    }

零钱兑换问题

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2:

输入: coins = [2], amount = 3 输出: -1

 public int coinChange(int[] coins, int amount) {
        // 零钱兑换,就动态规划,找到兑换i的最少钱数
        // dp[i] = min 遍历 dp[i-coins[j]] + 1
        if(coins == null || coins.length == 0){
            return -1;
        }
        int[] dp = new int[amount+1];
        for(int i=1;i<=amount;i++){
            // 这里最小的找钱次数是 amount + 1, 不要乱改
            int min = amount+1;
            for(int j=0;j<coins.length;j++){
                if(coins[j]<=i)
                min = Math.min(min,dp[i-coins[j]]+1);
            }
            dp[i] = min;
        }
        if (dp[amount] == amount+1){
            return -1;
        }
        return dp[amount];
    }

零钱兑换问题2

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2:

输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。

零钱兑换问题2 是完全背包问题

暴力求解

 public int change(int amount, int[] coins) {
        // 零钱兑换问题
        int[][] dp = new int[coins.length+1][amount+1];
        dp[0][0] = 1;
        for (int i=1;i<=coins.length;i++){
            for (int j=0;j<=amount;j++){
                for (int k=0;k*coins[i-1]<=j;k++){
                    dp[i][j] += dp[i-1][j-k*coins[i-1]];
                }
            }
        }
        return dp[coins.length][amount];
    }

再次进行优化, dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]];

完全背包

public int change(int amount, int[] coins) {
        // 零钱兑换问题
        int[][] dp = new int[coins.length+1][amount+1];
        for (int i=0;i<=coins.length;i++){
            dp[i][0] = 1;
        }
        for (int i=1;i<=coins.length;i++){
            for (int j=0;j<=amount;j++){
               dp[i][j] = dp[i-1][j];
               if(j > coins[i-1]){
                   dp[i][j] += dp[i][j-coins[i-1]];
               }
            }
        }
        return dp[coins.length][amount];
    }

将方法2中的dp[i][j] =dp[i - 1][j]+ dp[i][j - coins[i - 1]];dp[i][j]=dp[i−1][j]+dp[i][j−coins[i−1]];去掉一维ii得到,dp[j]=dp[j+dp[j-coins[i]]]dp[j]=dp[j+dp[j−coins[i]]]这里ii从00开始的,不需要取coins[i-1]coins[i−1]

这里因为状态之和前一个状态相关可以取消

public int change3rd(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
}

分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

注意: 这里应该从后向前推导,防止数据重用,在只有前i个物品是 j为3 是减了一遍sum[i], j 为8 还要减一遍;

    // 实际上可以转化为,子集中是否存在是二分之一的子集
    // 采用枚举的方法进行dfs搜索
   public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0){
            return false;
        }
        int sum = 0;
        for(int x:nums){
            sum += x;
        }
        if(sum % 2 == 1){
            return false;
        }
        // 子集分割实际为背包问题的变体
        boolean[] dp = new boolean[sum/2+1];
        dp[0] = true;
        for(int i=0;i<nums.length;i++){
            // 状态压缩后要注意遍历的顺序,这里每一个数字只能使用一次,所以应该从后往前推导
            for(int j=sum/2;j>=1;j--){
                if(j >= nums[i]){
                    dp[j] = dp[j] | dp[j-nums[i]];
                }
            }
        }
        return dp[sum/2];
    }

72. 编辑距离

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

插入一个字符 删除一个字符 替换一个字符

示例 1:

输入:word1 = "horse", word2 = "ros" 输出:3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')

 public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        
        int[][] dp = new int[len1+1][len2+1];

        for(int i=0;i<=len1;i++){
            dp[i][0] = i;
        }
        for(int i=0;i<=len2;i++){
            dp[0][i] = i;
        }
        for(int i=1;i<len1+1;i++){
            for(int j=1;j<len2+1;j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1;
                }
            }
        }
        return dp[len1][len2];
    }

高楼扔鸡蛋

若⼲层楼,若⼲个鸡蛋,让你算出最少的 尝试次数,找到鸡蛋恰好摔不碎的那层楼。

public int dp(int k, int n){
    int res = n + 1;
    for(int i=1;i<=n;i++){
        res = min(res,max(dp(k-1,i-1),dp(k,n-i))+1);
    }
}

最长公共子序列

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。 例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0。

示例 1:

输入:text1 = "abcde", text2 = "ace" 输出:3 解释:最长公共子序列是 "ace",它的长度为 3。

思路:当 s.char(i) == s1.char(j) 相等,dp[i][j] 与 dp[i-1][j-1] 状态有关

否则与 dp[i-1][j] 和 dp[i][j-1] 有关

    public  int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] dp = new int[len1+1][len2+1];
        for (int i=1;i<=len1;i++){
            for (int j=1;j<=len2;j++){
                if (text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else  {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[len1][len2];
    }

最长回文子序列

给定一个字符串s,找到其中最长的回文子序列,并返回该序列的长度。可以假设s的最大长度为1000。

示例 1: 输入:

"bbbab" 输出:

4

思路: 如果两个字符相同,当前的大小是 dp[i+1][j-1] + 2;

否则, dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);

 public int longestPalindromeSubseq(String s) {
        if(s.length() < 2){
            return s.length();
        }
        int[][] dp = new int[s.length()][s.length()];
        for (int i=0;i<s.length();i++){
            dp[i][i] = 1;
        }
        for (int i=s.length()-2;i>=0;i--){
            for (int j=i+1;j<s.length();j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][s.length()-1];
    }

正则表达式匹配

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

说明:

s 可能为空,且只包含从 a-z 的小写字母。 p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。 示例 1:

输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。

  public boolean isMatch(String s, String p) {
        int len1 = s.length();
        int len2 = p.length();
        if (len2 == 0){
            return len1 == 0;
        }
        boolean first_match = len1 > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
        if (p.length()>=2 && p.charAt(1) == '*'){
            // 匹配0个 或者多个
            return isMatch(s,p.substring(2)) || (first_match && isMatch(s.substring(1),p));
        }
        return first_match && isMatch(s.substring(1),p.substring(1));
    }
    public boolean isMatch(String s, String p) {
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        boolean[][] dp = new boolean[ss.length+1][pp.length+1];
        dp[0][0] = true;
        for (int i=1;i<=pp.length;i++){
            if (pp[i-1] == '*' && dp[0][i-2]){
                dp[0][i] = true;
            }
        }
        for (int i=1;i<=ss.length;i++){
            for (int j=1;j<=pp.length;j++){
                if (pp[j-1] == '*'){
                    if (pp[j-2] == ss[i-1] || pp[j-2] == '.'){
                        dp[i][j] = dp[i][j-1] || dp[i][j-2] || dp[i-1][j];
                    }else {
                        dp[i][j] = dp[i][j - 2];
                    }
                }else {
                    if (ss[i-1] == pp[j-1] || pp[j-1] == '.'){
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[ss.length][pp.length];
    }

四键键盘

4 种, 就是题⽬中提到的四个按键,分别是 A 、 C-A 、 C-C 、 C-V ( Ctrl 简 写为 C )。

   // 按 num 下键盘, 可以产生多长的字符

    public int maxA(int n, int num,int copy){
        if (n <= 0) return num;
        return Math.max(maxA(n-1,num+1,copy),
                Math.max(maxA(n-1,num+copy,copy),maxA(n-2,num,  num)));
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • top100习题

    根据每日 气温 列表,请重新生成一个列表,对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

    用户7625070
  • dp经典问题

    输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

    用户7625070
  • dp 类找零钱类问题

    这类问题,需要维护,之前的状态,当前的状态是 (当前 - 当前值) 的上一个状态的最值相关

    用户7625070
  • 算法细节系列(21):贪心有理?

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 程序员面试金典 - 面试题 16.17. 连续数列(DP/分治)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/contiguous-sequence-lcci 著...

    Michael阿明
  • 【LeetCode算法】两数之和

    LeetCode第一题:两数之和题目描述题目分析题目解答思路一:双重for循环(1)代码(2)提交结果思路二:hashmap键值对一次遍历(1)代码(2)提交结...

    程序员周同学
  • 漫画:动态规划系列 第二讲

    在上一篇文章中,我们讲解了DP的概念并且通过示例了解了什么是动态规划。本篇中,我们将继续通过1道简单题型,进一步学习动态规划的思想。

    程序员小浩
  • 初级算法-动态规划

    动态规划主要是解一些递归问题,也就是将递归写成非递归方式,因为编辑器无法正确对待递归,递归方法会导致很多计算结果被重复计算,比如菲波那切数列。

    方丈的寺院
  • 详解三道一维的动态规划算法题

    在一条直线上,有n个房屋,每个房屋中有数量不等的财宝,有一个盗 贼希望从房屋中盗取财宝,由于房屋中有报警器,如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问...

    帅地
  • 漫画:动态规划系列 第三讲

    在上一篇中,我们了解了什么是DP(动态规划),并且通过DP中的经典问题 "最大子序和",学习了状态转移方程应该如何定义。在本节中,我们将沿用之前的分析方法,通过...

    程序员小浩

扫码关注云+社区

领取腾讯云代金券