leetcode动态规划(字符串+递增子序列)

小鱼儿 2022-09-10 05:17 140阅读 0赞

1.  最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，\[3,6,2,7\] 是数组 \[0,3,1,6,2,2,7\] 的子序列。

输入：nums = \[10,9,2,5,3,7,101,18\]  
输出：4  
解释：最长递增子序列是 \[2,3,7,101\]，因此长度为 4 。

i到达新的位置时，搜索i之前的数值，如果i比之前的某个数值大，则更新dp数组为dp\[j\]+1，因为会有多个可能的较大的值，所有取最大值，即dp\[i\]=max(dp\[j\]+1,dp\[i\])。

class Solution {
        
        public int lengthOfLIS(int[] nums) {
        
            int l=nums.length;
            int[] dp=new int[l];
            dp[0]=1;
            int maxans=1;
            if(l==1){
        return 1;}
            for(int i=1;i<l;i++){
        
                dp[i]=1;
                for(int j=0;j<i;j++){
        
                    if(nums[i]>nums[j]){
        
                        dp[i]=Math.max(dp[j]+1,dp[i]);
                    }
                }
                maxans=Math.max(maxans,dp[i]);
            }
            return maxans;
        }
    }

1.  最长递增子序列的个数

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

示例 1:

输入: \[1,3,5,4,7\]  
输出: 2  
解释: 有两个最长递增子序列，分别是 \[1, 3, 4, 7\] 和\[1, 3, 5, 7\]。  
本题与上题的区别为输出最长子序列的个数，所以需要一个额外的count数组计数。  
先将dp数组和count数组的值都初始化为1。  
搜索过程同上，在nums\[i\]>nums\[j\]的前提下，如果dp\[j\]+1>dp\[i\]，说明是第一次找到了长度为n的子序列，将count\[i\]=count\[j\]。  
若dp\[j\]+1=dp\[i\]，则说明不是第一次找到了长度为n的子序列，则将count\[i\]+=count\[j\]。  
最后遍历一次数组，若dp\[i\]=maxlength，则将对应的count\[i\]加进结果。

class Solution {
        
        public int findNumberOfLIS(int[] nums) {
        
            int n = nums.length;
            if(n == 1) return 1;
    
            int[] dp = new int[n];
            int[] count = new int[n];
            Arrays.fill(dp, 1);
            Arrays.fill(count, 1);
            int maxLength = 0;
    
            for(int i = 1; i < n; i++){
        
                for(int j = 0; j < i; j++){
        
                    if(nums[i] > nums[j]){
        
                        if(dp[j] + 1 > dp[i]){
        //第一次找到
                            dp[i] = dp[j] + 1;
                            count[i] = count[j];
                        }else if(dp[j] + 1 == dp[i]){
        //又找到了
                            count[i] += count[j];
                        }
                    }
                }
                maxLength = Math.max(maxLength, dp[i]);
            }
    
            int res = 0;
            for(int i = 0; i < n; i++){
        
                if(dp[i] == maxLength){
        
                    res += count[i];
                }
            }
            return res;
        }
    }

1.  解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

‘A’ -> 1  
‘B’ -> 2  
…  
‘Z’ -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)
    "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

是上楼梯的变形，递推公式类似，i之前的一步可能是前一个数字单独编码的，也可能是前两个数进行编码。递推公式是dp\[i\]=dp\[i-1\]+dp\[i-2\]。  
但是边界条件需要额外确定，两位数的范围最大只为26.

class Solution {
        
        public int numDecodings(String s) {
        
            int n=s.length();
            s=" "+s;
            char[] cs=s.toCharArray();
            int[] dp=new int[n+1];
            dp[0]=1;
            for(int i=1;i<=n;i++){
        //上楼梯的变种，dp[i]=dp[i-1]+dp[i-2];
                int a=cs[i]-'0';
                int b=(cs[i-1]-'0')*10+a;
                //两个判断是并列进行的，因为存在两个都符合的可能。
                if(a>=1&&a<=9){
        
                    dp[i]+=dp[i-1];//前一个数字单独组成
                }
                if(b>=10&&b<=26){
        
                    dp[i]+=dp[i-2];//前两个数字可以组成
                }
            }//两个都符合的话就是上楼梯了。
            return dp[n];
        }
    }

1.  单词拆分

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

说明：

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

输入: s = “applepenapple”, wordDict = \[“apple”, “pen”\]  
输出: true  
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。  
注意你可以重复使用字典中的单词。

class Solution {
        
        public boolean wordBreak(String s, List<String> wordDict) {
        
            int n=s.length();
            boolean[] dp=new boolean[n+1];//dp数组表示n之前能否拆分
            dp[0]=true;//背包+动态规划
            for(int i=1;i<=n;i++){
        //遍历右边界
                for(int j=0;j<i;j++){
        //遍历左边界
                //在j之前可以被划分。并且wordict中包含s（j,i）的字串
                    if(dp[j]&&wordDict.contains(s.substring(j,i))){
        
                        dp[i]=true;//i之前也可以被划分
                        break;//退出当前循环，i继续向后。
                    }
                }
            }
            return dp[n];
        }
    }

1.  最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”  
输出：“bab”  
解释：“aba” 同样是符合题意的答案。  
用动态规划的方法来解决，dp\[ i \]\[ j \]表示从i到j的字串是否是回文串。  
递推过程，在type\[i\]==type\[j\]的前提下，i到j是否为回文串，取决于i+1带j-1是否为回文串。即dp\[ i \] \[ j \]

class Solution {
        
        public String longestPalindrome(String s) {
        
            int len=s.length();
            boolean dp[][]=new boolean[len][len];
            for(int i=0;i<len;i++){
        
                dp[i][i]=true;
            }
            int begin=0;int maxnum=1;
            int j;
            if(len<2)return s;
            char[] type=s.toCharArray();
            for(int l=2;l<=len;l++){
        //遍历长度
                for(int i=0;i<len;i++){
        //遍历左边界
                    j=l+i-1;//确定右边界
                    if(j>=len)break;
                    if(type[i]!=type[j])dp[i][j]=false;
                    else{
        
                        if(j-i<3)dp[i][j]=true;//只有3个即以下时，左右相等必是回文。
                        else{
        
                            dp[i][j]=dp[i+1][j-1];
                        }
                    }
                    if(dp[i][j]&&maxnum<j-i+1){
        
                    maxnum=j-i+1;
                    begin=i;
                }
                }
                
            }
            return s.substring(begin,begin+maxnum);
        }
    }