동적 계획 총화 및 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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.