동적 계획 총화 및 Leetcode 고전 문제 풀이

1666 단어 알고리즘
동적 계획
새로운 각도 에서 문 제 를 관찰 하고 문 제 를 바 꾸 어 재 귀 또는 전달 하 는 방식 으로 해결 할 수 있다 는 것 이다.최종 상태 에 이 르 기 위해 서 는 이전의 하나 또는 가장 좋 은 몇 가지 결과 에 근거 하여 이전의 상태 가 어떻게 이 루어 졌 든 지 간 에.1. 문 제 를 분리 하고 상태 와 상태 간 의 관 계 를 정의 함으로써 문 제 를 재 귀적 인 형식 으로 해결한다. 2. 핵심 은 상태의 정의 와 상태 전이 방정식 에 있다.
상태 전이 방정식 1. 상태 경계 상황 2. 상태 전이 방정식
동적 기획 문제 의 해답: 1. 문 제 를 전환 시 키 고 문제 와 하위 문 제 를 정의 한다. 2. 경계 상황 을 확정한다. 3. 상태 이동 방정식 을 확정한다. 4. 귀속 또는 추이 로 조작 한다.
Leet Code 5 의 가장 긴 답장 문자열 사고: 동적 계획 을 이용 하여 문자열 의 길이 가 1 또는 0 일 때 자 체 를 되 돌려 주 고 길이 가 2 인 문자열 부터 한 층 한 층 씩 답장 문자열 인지 여 부 를 판단 합 니 다. 조건 은 s [i] = s [j] 이 고 dp [i + 1] [j - 1] 이 진실 입 니 다.가장 긴 문자열 을 기억 할 때마다 가장 긴 문자열 을 찾 습 니 다.
public String longestPalindrome(String s) {
        int len=s.length();
        if(len==0||len==1)
            return s;

        String longest="";
        boolean[][]dp=new boolean[len][len];
        for(int i=len-1;i>=0;i--){
            for(int j=i;j

LeetCode 647 답문 하위 문자열 은 문자열 을 지정 합 니 다. 이 문자열 에 몇 개의 답문 하위 문자열 이 있 는 지 계산 하 는 것 이 작업 입 니 다.
서로 다른 시작 위치 나 끝 위 치 를 가 진 하위 문자열 은 같은 문자 로 구성 되 더 라 도 서로 다른 하위 문자열 로 계 산 됩 니 다.
예시 1:
입력: "abc" 출력: 3 설명: 세 개의 답장 하위 문자열: "a", "b", "c".
사고: 앞의 사고 와 마찬가지 로 판단 할 때 dp [i] [j] = true 는 결과 에 1 을 추가 합 니 다.
  public int countSubstrings(String s) {
        int len=s.length();
        if(len==0) return 0;
        if(len==1) return 1;
        int res=0;
        boolean[][]dp=new boolean[len][len];
        for(int i=len-1;i>=0;i--){
            for(int j=i;j

좋은 웹페이지 즐겨찾기