동적 기획/leetcode/직접 유도 추이 공식
583. Delete Operation for Two Strings
두 문자열에 대해 일정한 문자를 삭제하여 이 두 문자를 동일하게 하고 최소한의 삭제 수를 구합니다.
가장 긴 공통 서열을 구하는 문제로 바꿀 수 있습니다.두 문자열의 길이와 가장 긴 서열의 두 배를 구하면 된다.
가장 긴 공공 서브 서열의 동태적 계획에 대한 이해는 먼저 자정에서 아래로 돌아가는 방법부터 이해해야 한다.
참조 링크는 모든 방법을 제공합니다.https://leetcode.com/problems/delete-operation-for-two-strings/solution/
안에서 먼저 귀속 방법을 소개한 다음에 귀속을 바탕으로 수조를 저장하는 방법을 소개한 다음에 동적 기획 방법을 소개하고 가장 긴 서열로 전환되지 않는 동적 기획 방법을 소개했다.일반적인 압축 방법도 소개했다.
다음은 최장자 서열의 2차원 동태 기획 방법이다.
class Solution {
public:
int minDistance(string word1, string word2) {
vector> dp(word1.size()+1,vector(word2.size()+1,0));// ， ，
for(int i=0;i<=word1.size();i++)
for(int j=0;j<=word2.size();j++)
{
if(i==0||j==0) continue;
if(word1[i-1]==word2[j-1])//
dp[i][j]=dp[i-1][j-1]+1;
else
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
return word1.size()+word2.size()-2*dp[word1.size()][word2.size()];
}
}; 413 Arithmetic slices 등차수열 슬라이스 배열(연속 하위 시퀀스)
제목: 하나의 그룹의 연속 하위 그룹을 찾아서 이 하위 그룹을 등차 수열로 만듭니다.이 피드 그룹의 개수를 요청합니다.
나의 사고방식
(1) n방의 복잡도는 우선 누적과 수조를 구한 다음에 등차수열에 따라 요건을 구하고 서열이 등차수열인지 아닌지를 판단하지만 해고는 옳지 않다
class Solution {
public:
int numberOfArithmeticSlices(vector& A) {
int n=A.size();
if(n<=2) return 0;
vector sum(n+1,0);
//
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+A[i-1];
int count=0;
for(int i=3;i<=n;i++)
{
for(int k=3;i-k>=0;k++)
{
int cursum=sum[i]-sum[i-k];
if((cursum-k*A[i-k])%(k*(k-1)/2)==0)
count++;
}
}
return count;
}
}; dp[i]를 설정하면 i1개까지 표시할 때 앞에 구성된 수열 개수,
만약에 A[i-1]-A[i-2]==A[i-2]-A[i-3]dp[i]=dp[i-1]+1+(len-2)+1이면 여기의len은 앞에서 적어도 3개의 수를 셀 때의 길이 3이고 앞에 등차 서열이 구성되지 않으면len=0, 공식은 dp[i]=dp[i-1]+1으로 바뀐다.
만약에 A[i-1]-A[i-2]!=A[i-2]-A[i-3], dp[i]=dp[i-1]는 이때 렌을 0으로 만든다.
class Solution {
public:
int numberOfArithmeticSlices(vector& A) {
int n=A.size();
vector dp(n+1,0);
int len=0;
for(int i=3;i<=n;i++)
{
if(A[i-1]-A[i-2]==A[i-2]-A[i-3])
{
if(len==0)// ， 3
{
dp[i]=dp[i-1]+1;
len=3;// len
}
else//
{
dp[i]=dp[i-1]+len-1;
len++;//len
}
}
else
{
dp[i]=dp[i-1];
len=0;//
}
}
return dp[n];
}
}; dp를 변수로 압축할 수 있습니다.
class Solution {
public:
int numberOfArithmeticSlices(vector& A) {
int n=A.size();
int dp=0;
int len=0;
for(int i=3;i<=n;i++)
{
if(A[i-1]-A[i-2]==A[i-2]-A[i-3])
{
if(len==0)
{
dp=dp+1;
len=3;
}
else
{
dp=dp+len-1;
len++;
}
}
else
{
dp=dp;
len=0;
}
}
return dp;
}
}; 참조 방법:
(1)dp[i]는 i로 끝나는 등차수 열의 개수를 나타낸다. 만약에 A[i]-A[i-1]=A[i-1]-A[i-2], dp[i]=dp[i-1]+1;그렇지 않으면 dp[i]=0
class Solution {
public:
int numberOfArithmeticSlices(vector& A) {
int res = 0, n = A.size();
vector dp(n, 0);
for (int i = 2; i < n; ++i) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = dp[i - 1] + 1;
}
res += dp[i];
}
return res;
}
}; 상술한 dp는 매번 현재 값과 앞의 값만 관련되기 때문에 하나의 변수로 대체할 수 있다.
class Solution {
public:
int numberOfArithmeticSlices(vector& A) {
int res = 0, cur = 0;
for (int i = 2; i < A.size(); ++i) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
cur += 1;
res += cur;
} else {
cur = 0;
}
}
return res;
}
}; [1,2,3,4] 길이가 적어도 3인 산수 슬라이스 3개를 함유하고 있는데 [1,2,3,4,5]가 몇 개인지 다시 봅시다.
len = 3: [1,2,3], [2,3,4], [3,4,5]
len = 4: [1,2,3,4], [2,3,4,5]
len = 5: [1,2,3,4,5]
그러면 우리는 추이식을 찾아낼 수 있다. 길이가 n인 등차수열에 길이가 적어도 3인 산수절편의 개수는 (n-1)(n-2)/2이다. 그러면 제목은 원수조 중의 등차수열의 길이를 찾은 다음에 공식을 가지고 개수를 계산하면 된다.
다음 코드count=1은 길이가 3임을 나타낸다.
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
int count = 0;
int sum = 0;
for (int i = 2; i < A.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {// ， ，1 3，2 4
count++;
} else {
sum += (count + 1) * (count) / 2;// ，
count = 0;// count 0
}
}// ， ，
return sum += count * (count + 1) / 2;// ， ， 。 ，count 0
}
}class Solution {
public:
int numberOfArithmeticSlices(vector& A) {
int res = 0, len = 2, n = A.size();
for (int i = 2; i < n; ++i) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
++len;
} else {
if (len > 2) res += (len - 1) * (len - 2) * 0.5;
len = 2;
}
}
if (len > 2) res += (len - 1) * (len - 2) * 0.5;
return res;
}
}; 446. Arithmetic Slices II - Subsequence 등차 수열 슬라이스 시퀀스(연속하지 않을 수 있음)
646 maxmum length of pair chain pair의 최대 체인
n조의 수를 정하고 각 조의 첫 번째 수는 두 번째 수보다 작다.만약 두 개의 그룹이 첫 번째 그룹의 큰 값이 두 번째 그룹의 작은 값보다 작다면 하나의 체인을 구성한다.제목은 가장 큰 체인의 길이를 되돌려 달라고 합니다.
343 인덱스 브레이크 정수 절분 곱셈 최대
한 수를 몇 수의 합으로 나눌 수 있는데, 이 수를 곱하는 최대치는 얼마입니까?
357 Count Numbers with Unique Digits
하나의 수 n을 정하고 0≤x<10n에서 모든 수를 찾으면 같은 숫자가 없습니다
486 Predict the Winner 카드 게임 문제
제목: 정수 그룹 A가 있는데 수치가 다른 카드를 대표하여 한 줄로 배열되어 있다.유저 a와 유저 b는 순서대로 모든 카드를 가져간다. 유저 a가 먼저 들고 유저 b가 나중에 가지도록 규정한다. 그러나 모든 유저는 매번 가장 왼쪽 또는 가장 오른쪽의 카드를 가져갈 수 밖에 없다. 유저 a와 유저 b는 모두 매우 총명하다. 그들은 항상 가장 좋은 전략을 채택한다.최종 우승자의 점수를 돌려주세요.카드 시퀀스 A와 시퀀스 크기 n을 지정하면 마지막 점수가 높은 자의 점수를 되돌려 주십시오. (같은 것은 임의의 점수를 되돌려 줍니다.)(획득한 카드 수 추가)
아이디어:
반복 유도:
// class Solution {
public:
bool PredictTheWinner(vector& nums) {
int sum=accumulate(nums.begin(),nums.end());
int me=p(nums,0,nums.size()-1);
if(sum-me>=me) return false;
else
return true;
}
//
int p1(vector& nums,int i,int j)//i ，j
{
// i， j
// ，
if(i==j) return nums[i];
// ，
if(i=j-1) return max(nums[i],nums[j]);
int sum=0;
// i， i-1 j， i-2 j，
// i ，
//p(nums,i+2,j),p(nums,i+1,j-1);
// :min(p(nums,i+2,j),p(nums,i+1,j-1))
// , j
// ：i j-1. ：min(p(nums,i+1,j-1),p(nums,i,j-2))
// ， ：
return max(nums[i]+min(p(nums,i+2,j-1),p(nums,i+1,j-1)),nums[j]+min(p(nums,i+1,j-1),p(nums,i,j-2)));
}
}; class Solution {
public:
bool PredictTheWinner(vector& nums) {
int sum=std::accumulate(nums.begin(),nums.end(),0);
int n=nums.size();
if(n==1) return true;
vector> dp(n,vector(n,0));
for(int i=n-1;i>=0;i--)
{
for(int j=i;j 1차원 그룹으로 변경: 왼쪽 아래의 반사 대각선에 의존하기 때문에 왼쪽 위에서 오른쪽 아래로 반사 대각선을 따라 옮겨야 한다
표준 답안:
그의 귀착된 사고방식은 그다지 같지 않다https://leetcode.com/problems/predict-the-winner/solution/
464Can I Win
주어진 범위에서 매번 두 사람이 번갈아 한 수를 꺼낸다. 이 수를 합치면 목표수보다 클 때 그 사람이 이긴다. 첫 번째로 수를 잡은 사람이 이길 수 있느냐고 묻는다.만약 두 사람이 모두 늘 총명하다고 가정한다면
375Guess Number Higher or Lower II
맞혀봐, 얼마를 쓰면 얼마를 가져가면 맞힐 수 있냐고?
392 Is Subsequence는 문자열이 다른 문자열의 하위 시퀀스인지 여부를 판단합니다.
494 target Sum
이 문제는 우리에게 하나의 수조와 하나의 목표 값을 주었다. 우리는 수조의 모든 숫자에 정호나 음호를 더한 다음에 목표 값과 같아야 하는지, 얼마나 다른 상황이 있는지 구하자.
650 2 Keys Keyboard
텍스트에는 한 글자 A만 있고, 매번 동작은 현재 모든 숫자를 복사하여 붙이거나 다시 붙여넣을 수 있으며, 문자의 길이를 정하는 데 필요한 최소 작업 횟수를 구할 수 있습니다
추측을 통해 규칙을 찾으면 dp[i]:if(k*j=i)dp[i]=min(dp[k]+dp[j])을 발견할 수 있다. 즉, 한 수의 조작 횟수는 그 곱셈 인자의 조작수의 합과 같고 sqrt에서 가장 가까운 두 인수를 찾으면 된다.
class Solution {
public:
int minSteps(int n) {
//dp[i]:if(k*j==i) dp[i]=min(dp[k]+dp[j])
if(n<=1) return 0;
vector dp(n+1,0);
dp[1]=0;
for(int i=2;i<=n;i++)
{
dp[i]=i;
int factor=sqrt(i);
for(int j=factor;j>0;j--)
{
if(i%j==0) {
dp[i]=dp[j]+dp[i/j];
break;
}
}
}
return dp[n];
}
}; 또 다른 해법:
2*2=2+2,2*3>2+3,4*4>4+4이기 때문에 이전의 그런 방법에서 얻은 두 인자는 각각 분해할 수 있다.이 제목은 한 수를 여러 인자로 분해하는 가화에 해당한다.예를 들어 30->5+6,6->2+3, 바로 2+3+5.그래서 귀속적으로 실현할 수 있다.
class Solution {
public:
int minSteps(int n) {
if (n == 1) return 0;
for (int i = 2; i < n; i++)
if (n % i == 0) return i + minSteps(n / i);
return n;
}
}; public int minSteps(int n) {
int s = 0;
for (int d = 2; d <= n; d++) {
while (n % d == 0) {
s += d;
n /= d;
}
}
return s;
}377 Combination Sum IV
하나의 집합을 정하고, 각각의 수가 다르며, 하나의 목표를 정하고, 집합에서 선택수(중복 가능)의 가화는 이 목표 값이다. 몇 가지가 있느냐고 묻는다. (순서가 다른 것은 같은 종류가 아니다.)
https://discuss.leetcode.com/topic/52302/1ms-java-dp-solution-with-detailed-explanation본고는 자정향하의 귀속과 자저상향의 동태적 계획을 설명하였다.
class Solution {
public:
int combinationSum4(vector& nums, int target) {
int n=nums.size();
vector com(target+1,0);
com[0]=1;
for(int i=1;i<=target;i++)
for(int j=0;j=0)
com[i]+=com[i-nums[j]];// i nums （ ）， com[i] （ ）
}
return com[target];
}
}; 638 Shopping Offers
할인 판촉 조합은 구매해야 할 상품의 유형과 수량을 정하여 이 물건들을 사는데 쓰는 최소한의 돈을 구한다
309 Best Time to Buy and Sell Stock with Cooldown
덤핑 주식을 마음대로 살 수 있지만 덤핑 후 하루는 주식을 살 수 없으니 돈을 얼마나 벌까?
416 Partition Equal Subset Sum은 하나의 배열을 두 그룹으로 나누어 두 그룹의 요소를 가화할 수 있느냐고 물었다
376 Wiggle Subsequence 최장자 시퀀스 증감
이 문제 본 문제풀이
아이디어 1:
up[i]를 설정하면 i위치에서 첫 번째 값이 플러스인 진동자 서열의 최대 길이를 표시하고,down[i]는 i위치에서 첫 번째 값이 마이너스인 진동자 서열의 최대 길이를 각각 up[i]가 이전의 down[j]를 옮겨다니며,nums[i]>nums[j]가 충족되면 up[i]를 업데이트할지 여부를 선택합니다
모든down[i]이 이전 up[j]를 옮겨다니면서nums[i]
class Solution {
public:
int wiggleMaxLength(vector& nums) {
int n=nums.size();
if(n<=1) return n;
vector up(n,1);// 1
vector down(n,1);
for(int i=1;inums[j])
{
up[i]=max(up[i],down[j]+1);
}
else if(nums[i] 아이디어 2:
만약nums[i]>nums[i-1]라면up[i]=down[i-1]+1,down[i]=down[i-1]
만약nums[i]>nums[i-1]라면down[i]=up[i-1]+1,up[i]=up[i-1]
만약 둘이 같다면down[i]=down[i-1]up[i]=up[i-1]
한 번만 훑어보면 돼요.down[0]과 up[0]는 모두 1입니다.
class Solution {
public:
int wiggleMaxLength(vector& nums) {
int n=nums.size();
if(n<=1) return n;
vector up(n,0);// 1
vector down(n,0);
down[0]=1;
up[0]=1;
for(int i=1;inums[i-1])
{
down[i]=up[i-1]+1;
up[i]=up[i-1];
}
if(nums[i]==nums[i-1])
{
down[i]=down[i-1];
up[i]=up[i-1];
}
}
return max(up[n-1],down[n-1]);
}
}; 욕심 알고리즘:
증감 곡선을 고려할 때 우리는 점을 찾을 때 연속 승차순이나 연속 강차를 만났을 때 반드시 이 단락의 두 노드만 선택할 수 있고 증감이 나타날 때 이런 부분도 포함된다.이 제목은 원래의 노드를 일종의'필터 처리'로 해석할 수 있다. 노드의 역할은 추세 변화의 증감 특징만 묘사하고 일정 시간 동안 연속적으로 증가하거나 감소할 때 우리는 이 단락의 시작과 끝에만 관심을 가지며 중간의 과정을 소홀히 한다.
public class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2)
return nums.length;
int prevdiff = nums[1] - nums[0];
int count = prevdiff != 0 ? 2 : 1;
for (int i = 2; i < nums.length; i++) {
int diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
count++;
prevdiff = diff;
}
}
return count;
}
}368 Largest Divisible Subset은 최대 서브집합을 구하고 서브집합의 임의의 두 수 중 하나가 다른 수에 의해 제거될 수 있는 264 Ugly Number II는 n번째 추수를 구한다
467 Unique Substrings in Wraparound String
576 Out of Boundary Paths
322 Coin Change
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
