動(dòng)態(tài)規(guī)劃常見問題
零、組合問題
1、硬幣問題
n=len(arr)
? ? ? ? if n<=0 or aim<=0:
? ? ? ? ? ? return 0
? ? ? ? dp=[float("inf")]*(aim+1)
? ? ? ? dp[0]=0
? ? ? ? for i in range(n):
? ? ? ? ? ? for j in range(arr[i],aim+1):
? ? ? ? ? ? ? ? dp[j]=min(dp[j],dp[j-arr[i]]+1)
? ? ? ? return dp[aim] if dp[aim]!=float("inf") else -1
https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45?tpId=117&&tqId=37795&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
一、子序列、字串問題
1、最長連續(xù)字串
res = ""
? ? ? ? maxlen = 0
? ? ? ? for i in range(len(str1)):
? ? ? ? ? ? if str1[i-maxlen : i+1] in str2:
? ? ? ? ? ? ? ? res = str1[i-maxlen:i+1]
? ? ? ? ? ? ? ? maxlen = maxlen + 1
? ? ? ? return res
https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=117&&tqId=37799&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
2、最長子序列（不要求連續(xù)）長度
m, n = len(text1), len(text2)
? ? ? ? dp = [[0] * (n + 1) for _ in range(m + 1)]
? ? ? ? for i in range(1, m + 1):
? ? ? ? ? ? for j in range(1, n + 1):
? ? ? ? ? ? ? ? if text1[i - 1] == text2[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 dp[m][n]
https://leetcode-cn.com/problems/longest-common-subsequence/
3、最長子序列（不要求連續(xù)）
m=len(s1)
? ? ? ? n=len(s2)
? ? ? ? dp=[["" for j in range(n+1)] for i in range(m+1)]
? ? ? ? for i in range(m):
? ? ? ? ? ? for j in range(n):
? ? ? ? ? ? ? ? if s1[i]==s2[j]:
? ? ? ? ? ? ? ? ? ? dp[i+1][j+1]=dp[i][j]+s1[i]
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? if len(dp[i][j+1])>len(dp[i+1][j]):
? ? ? ? ? ? ? ? ? ? ? ? dp[i+1][j+1]= dp[i][j+1]?
? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? dp[i+1][j+1]= dp[i+1][j]
? ? ? ? return? dp[m][n] if dp[m][n]!="" else "-1"
https://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11?tpId=117&&tqId=37798&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
二、股票交易問題
二次交易
if len(prices)<=1:
? ? ? ? ? ? return 0
? ? ? ? k=len(prices)
? ? ? ? #定義最大收益
? ? ? ? dp0=[0]*k
? ? ? ? dp1=[0]*k
? ? ? ? dp2=[0]*k
? ? ? ? dp3=[0]*k
? ? ? ? dp4=[0]*k
? ? ? ? dp0[0]=0
? ? ? ? dp1[0]=-prices[0]
? ? ? ? dp2[0]=0
? ? ? ? dp3[0]=-prices[0]
? ? ? ? dp4[0]=0
? ? ? ? for i in range(1,k):
? ? ? ? ? ? dp0[i]=dp0[i-1]
? ? ? ? ? ? dp1[i]=max(dp1[i-1],dp0[i-1]-prices[i])
? ? ? ? ? ? dp2[i]=max(dp2[i-1],dp1[i-1]+prices[i])
? ? ? ? ? ? dp3[i]=max(dp3[i-1],dp2[i-1]-prices[i])
? ? ? ? ? ? dp4[i]=max(dp4[i-1],dp3[i-1]+prices[i])
? ? ? ? return dp4[k-1]
https://www.nowcoder.com/practice/4892d3ff304a4880b7a89ba01f48daf9?tpId=117&&tqId=37847&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
三、子數(shù)組最大乘積
核心的關(guān)鍵是：判斷當(dāng)前值的正負(fù)以及需要兩個(gè)狀態(tài)
k=len(arr)
? ? ? ? dpmax=[0]*k
? ? ? ? dpmin=[0]*k
? ? ? ? if k==0:
? ? ? ? ? ? return
? ? ? ? if k==1:
? ? ? ? ? ? return arr[0]
? ? ? ? dpmax[0]=arr[0]
? ? ? ? dpmin[0]=arr[0]
? ? ? ? maxsum=arr[0]
? ? ? ? for i in range(1,k):
? ? ? ? ? ? if arr[i]>0:
? ? ? ? ? ? ? ? dpmax[i]=max(arr[i],arr[i]*dpmax[i-1])
? ? ? ? ? ? ? ? dpmin[i]=min(arr[i],arr[i]*dpmin[i-1])
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? dpmax[i]=max(arr[i],arr[i]*dpmin[i-1])
? ? ? ? ? ? ? ? dpmin[i]=min(arr[i],arr[i]*dpmax[i-1])
? ? ? ? ? ? maxsum=max(maxsum,dpmax[i])
? ? ? ? return maxsum
https://www.nowcoder.com/practice/9c158345c867466293fc413cff570356?tpId=117&&tqId=37785&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
四、字符串的全排
res=[]
? ? ? ? c=list(ss)
? ? ? ? k=len(c)
? ? ? ? if k==1:
? ? ? ? ? ? return c
? ? ? ? else:
? ? ? ? ? ? for i in range(k):
? ? ? ? ? ? ? ? first=str(c[i])
? ? ? ? ? ? ? ? for tmp in self.Permutation(''.join(c[:i]+c[i+1:])):
? ? ? ? ? ? ? ? ? ? second=''.join(tmp)
? ? ? ? ? ? ? ? ? ? s=first+second
? ? ? ? ? ? ? ? ? ? if s not in res:
? ? ? ? ? ? ? ? ? ? ? ? res.append(s)
? ? ? ? return res
https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=117&&tqId=37778&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
leetcode:567字符串的排列
https://leetcode-cn.com/problems/permutation-in-string/
雙指針
劍指offer38:字符串的排列
https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
回溯法
https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/
https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/
