題目匯總

以下鏈接均為我博客內(nèi)對應(yīng)博文，有解題思路和代碼，不定時更新補充。

目前范圍：Leetcode前150題

動態(tài)規(guī)劃題目

一維DP

一維DP需要的就是清晰的思路，每個題都變化很大

• Longest Valid Parentheses/最長有效括號
  找出一個只包含”(“和”)”的字符串中最長的有效子字符串的長度。有效的意思是指該子字符串中的括號都能正確匹配。

• Maximum Subarray/ 最大子序和
  由 N 個整數(shù)元素組成的一維數(shù)組 (A[0], A[1],…,A[n-1], A[n])，這個數(shù)組有很多連續(xù)子數(shù)組，那么其中數(shù)組之和的最大值是什么呢？

• Climbing Stairs/爬樓梯
  一共有n級樓梯，每次能夠爬一級或兩級，共有多少種不同的爬法爬到頂端。注意：第一級樓梯也要上，也就是說第二個樓梯就有兩種走法。

• Decode Ways/解碼方法
  現(xiàn)在有如下的字母與數(shù)字的對應(yīng)關(guān)系：1-A, 2-B, …26-Z。給定一個由數(shù)字組成的字符串，判斷按照上面的映射可以轉(zhuǎn)換成多少種不同的字符串。(比爬樓梯需要多考慮情況)

• Unique Binary Search Trees/不同的二叉查找樹
  給出一個n，求1-n能夠得到的所有二叉搜索樹

• Triangle/三角形最小路徑和
  將一個二維數(shù)組排列成金字塔的形狀，找到一條從塔頂?shù)剿椎穆窂?，使路徑上的所有點的和最小，從上一層到下一層只能挑相鄰的兩個點中的一個。

• Palindrome Partitioning/Palindrome Partitioning II/分割回文串/分割回文串II
  將一個字符串分割成若干個子字符串，使得子字符串都是回文字符串，要求最少需要幾次分割能夠滿足需求。

• Word Break/Word Break II/單詞拆分/單詞拆分 II
  給定一個目標字符串和一組字符串，判斷目標字符串能否拆分成數(shù)個字符串，這些字符串都在給定的那組字符串中。

• Best Time to Buy and Sell Stock I/II/III/買賣股票的最佳時機
  給定每天的股票價格，如果只允許進行一輪交易，也就是買進一次和賣出一次，求所能獲得的最大的利潤。

二維DP

布爾數(shù)組

• Longest Palindromic Substring/最長回文子串
  給出一個字符串S，找到一個最長的連續(xù)回文串。

• Interleaving String/交錯字符串
  輸入三個字符串s1、s2和s3，判斷第三個字符串s3是否由前兩個字符串s1和s2交替而成且不改變s1和s2中各個字符原有的相對順序。

數(shù)字數(shù)組

• Unique Paths/Unique Paths II/不同路徑
  機器人從起點到終點有多少條不同的路徑，只能向右或者向下走。

• Minimum Path Sum/最小路徑和
  一個矩陣的左上角出發(fā)到右下角，只能向右或向下走，找出哪一條路徑上的數(shù)字之和最小。

• Edit Distance/編輯距離
  求兩個字符串之間的最短編輯距離，即原來的字符串至少要經(jīng)過多少次操作才能夠變成目標字符串，操作包括刪除一個字符、插入一個字符、更新一個字符。

• Distinct Subsequences/不同子序列
  給定S和T兩個字符串，問把通過刪除S中的某些字符，把S變?yōu)門有幾種方法？

• 補充：京東2019實習編程題-刪除0或部分字符使其成為回文串
  見筆試整理總結(jié)

• 補充：愛奇藝2019實習編程題-n種糖果，每個盒子m個，每個糖果有最小最大限制，求多少種放法
  見網(wǎng)頁

三維DP

• Scramble String/擾亂字符串
  給出兩個等長的字符串 s1 和 s2，判斷 s2 是否是 s1 的擾亂字符串。

動態(tài)規(guī)劃總結(jié)