leetcode-동적 기획 3

오늘은 동태적인 계획을 세우고 미친 듯이 이성을 잃는 날이다.동적 기획은 바로 뒷걸음질로 앞걸음질을 해야 하는 결과139.단어 분할은 비공식 문자열 s와 비공식 단어 목록을 포함하는 사전wordDict를 지정하여 s가 빈칸에서 한 개 이상의 사전에 나오는 단어로 분할될 수 있는지 여부를 판정합니다.분할할 때 사전의 단어를 반복해서 사용할 수 있다.너는 사전에 중복된 단어가 없다고 가정할 수 있다.이 문제의 사고방식은 이전에 잔돈을 모으고 완전 제곱수를 모으는 것과 해법이 유사하다. 모두 n단계일 때 여러 가지 n-1단계의 상황이 있기 때문에 서로 다른 상황을 두루 겪은 다음에 최소한의 만족 상황을 선택해야 한다.일반적으로 dp[n]를 구하는 대로 기록을 한다. 예를 들어 이런 문제는 분리할 수 있는지, dp[i]는 0에서 i까지의 문자열을 분리할 수 있는지, 예를 들어 몇 가지 방법을 구하는지, dp[i]는 i를 모으는 몇 가지 방법이 있는지 기록한다.

class Solution {
         
public boolean wordBreak(String s, List<String> wordDict) 
{
     //dp[n]=dp[n]||dp[n-word]
boolean []dp=new boolean [s.length()+1];
for(int i=1;i<=s.length();i++)
dp[i]=false;dp[0]=true;
for(int i=1;i<=s.length();i++){
         
for(String word:wordDict){
         
if(i-word.length()>=0&&dp[i]==false)    {
             
String temp=s.substring(0,i);        
if(temp.equals(s.substring(0,i-word.length())+word))    
dp[i]=dp[i]||dp[i-word.length()];//   dp[i]                           }    
}}  
return dp[s.length()];    }    }

300. 최장 상승 서열은 무질서한 정수 그룹을 정하고 그 중에서 가장 긴 상승 서열의 길이를 찾습니다.이와 유사하게 dp[i]는 i의 가장 긴 길이를 기록한 다음에 여기에 여러 n-1보의 상황이 나타나지 않는다. 이 수보다 작은 그 수의 길이를 1로 늘리기만 하면 된다.

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

91. 디코딩 방법 중 알파벳 A-Z가 포함된 메시지는 다음과 같은 방식으로 인코딩되었다.'A'->1'B'->2... 이 문제도 dp[i]에서 i위를 기록하는 몇 가지 인코딩이 있다. 이 문제는 사실 모든 것이 하나의 가능성이 있다. 바로 n위가 확정된 것이다. n-1위와의 조합은 하나의 결과이기 때문에 두루 훑을 필요가 없다. 그러나 이런 문제는 많은 상황을 고려해야 하기 때문에 상태 방정식을 잘 고려해야 한다.dp[i]=dp[i-2] i=0&(i-1=1|i-1=2) dp[i]=dp[i-1]+dp[i-2] (i-1=1|i-1=2&<0i<7)&i!=0 dp[i]=dp[i-1] otherwise

class Solution {
         public int numDecodings(String s) {
             int []res=new int [s.length()+1];        res[0]=1;        if(s.charAt(0)!='0')        {
     res[1]=1;}        else return 0;        for(int i=1;i<s.length();i++)        {
                 if(s.charAt(i)=='0')            {
     if(s.charAt(i-1)=='1'||s.charAt(i-1)=='2')            res[i+1]=res[i-1];            else return 0;}            else if(s.charAt(i-1)=='1'||(s.charAt(i-1)=='2'&&s.charAt(i)>'0'&&s.charAt(i)<'7'))            res[i+1]=res[i-1]+res[i];            else res[i+1]=res[i];        }        return res[s.length()];    }}

152. 곱셈이 가장 큰 서열은 정수 수조nums를 정하고 한 서열에서 곱셈이 가장 큰 연속 서열을 찾아낸다(이 서열은 최소한 한 개의 수를 포함한다).이 문제 해법은 좀 까다로워서 공부를 했다

class Solution {
         public int maxProduct(int[] nums) {
             int max=1,min=1,maxlen=Integer.MIN_VALUE;        for(int i=0;i<nums.length;i++)        {
                 if(nums[i]<0)            {
                     int temp=min;                min=max;                max=temp;            }            max=Math.max(nums[i]*max,nums[i]);            min=Math.min(nums[i]*min,nums[i]);            maxlen=Math.max(max,maxlen);        }        return maxlen;    }}