字符串、回文数、求相同，这些其实天然地就和动态规划很贴合的 1、最长重复子数组
/** * @param {number[]} A * @param {number[]} B * @return {number} */ var findLength = function(A, B) { let dp = new Array(A.length + 1) for(let i = 0; i < dp.length; i++) { dp[i] = new Array(B.length + 1).fill(0) } let max = 0 for(let i = 1; i < dp.length; i++) { for(let j = 1; j < dp[0].length; j++) { if(A[i - 1] === B[j - 1]) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1) max = Math.max(max, dp[i][j]) } } } return max };2、恢复空格
/** * @param {string[]} dictionary * @param {string} sentence * @return {number} */ var respace = function(dictionary, sentence) { let dp = new Array(sentence.length + 1).fill(0) for(let i = 1; i < dp.length; i++) { // 最坏情况，重要 dp[i] = dp[i - 1] + 1 for(let word of dictionary) { if(word.length <= i) { if(sentence.substring(i - word.length, i) === word) { dp[i] = Math.min(dp[i], dp[i - word.length]) } } } } return dp[sentence.length] };