【技术积累】算法中的动态规划【一】 全球今热点

initialize dp[] with value 1for i from 1 to n:    for j from 0 to i-1:        if nums[i] > nums[j]:            dp[i] = max(dp[i], dp[j]+1)max_len = max(dp[0...n-1])return max_len

给定一个整数序列，从中找到一个子序列，使得该子序列中的元素之和最大。

确定状态： 因为子序列的长度不确定，所以状态可以由子序列的结尾元素来描述。假设以第i个元素结尾的子序列的最大和为f(i)，则要求的最终结果为max{f(i)}

确定状态转移方程： 对于以第i个元素结尾的子序列，有两种情况：

确定初始值： 初始值需满足转移方程的要求，可以令f(0)=0

确定计算顺序： 计算顺序为从左到右，即从小到大

maxSubArray(A):n = A.length// 初始化f[0] = 0maxS = A[0]// 状态转移for i from 1 to n:f[i] = max(f[i-1] + A[i], A[i])// 更新全局最优解maxS = max(maxS, f[i])return maxS

给定n个矩阵{A1, A2, …, An}，其中Ai的规模为pi-1 x pi（i=1,2,…,n），求完全括号化矩阵乘积A1A2…An的最小计算次数。

状态表示：定义动态规划状态dp[i][j]表示从第i个矩阵乘到第j个矩阵所需的最小计算次数。

状态转移方程：对于i<= k < j，其中k代表第一个矩阵乘的序号，可以得到状态转移方程：dp[i][j] = min{dp[i][k] + dp[k+1][j] + pi-1 pk pj}。

初始状态：对于只有一个矩阵的情况，最小计算次数为0，即dp[i][i] = 0。

计算顺序：按照矩阵乘法的顺序计算dp[i][j]，需要先计算dp[i][i+1]、dp[i][i+2]、dp[i][i+3]等子问题，再计算dp[i][i+2]、dp[i][i+3]、dp[i][i+4]等子问题，以此类推。

最终结果：所求的结果为dp[1][n]。

function matrixChainOrder(p):n = length(p) - 1  // 矩阵个数let dp[1..n, 1..n] be a new tablefor i = 1 to n:dp[i][i] = 0  // 初始化对角线元素为0for L = 2 to n:  // L为子问题矩阵乘法长度for i = 1 to n-L+1:j = i + L - 1dp[i][j] = +∞  // 初始化为正无穷for k = i to j-1:q = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]if q < dp[i][j]:dp[i][j] = qreturn dp[1][n]

给定两个字符串A和B，求出将A转换成B所需的最小编辑次数（一次编辑包括插入、删除、替换操作）。

确定状态：定义dp[i][j]表示将A的前i个字符转换成B的前j个字符所需的最小编辑次数。

初始化：dp[i][0] = i，表示将A的前i个字符转换成空字符串所需的编辑次数；dp[0][j] = j，表示将空字符串转换成B的前j个字符所需的编辑次数。

状态转移方程：若A[i] == B[j]，dp[i][j] = dp[i-1][j-1]；否则，需要考虑以下三种情况：

返回结果：最终结果为dp[len(A)][len(B)]，其中len(A)表示字符串A的长度，len(B)表示字符串B的长度。

function minEditDistance(strA, strB) {let lenA = length(strA), lenB = length(strB);let dp[lenA+1][lenB+1];for (let i = 0; i <= lenA; i++) {dp[i][0] = i;}for (let j = 0; j <= lenB; j++) {dp[0][j] = j;}for (let i = 1; i <= lenA; i++) {for (let j = 1; j <= lenB; j++) {if (strA[i-1] == strB[j-1]) {dp[i][j] = dp[i-1][j-1];} else {dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1;}}}return dp[lenA][lenB];}

给定两个字符串S和T，求它们的最长公共子序列。

function longestCommonSubsequence(S, T) {let dp = new Array(S.length + 1).fill(0).map(() => new Array(T.length + 1).fill(0));for(let i = 1; i <= S.length; i++) {    for(let j = 1; j <= T.length; j++) {        if(S[i - 1] == T[j - 1]) {            dp[i][j] = dp[i - 1][j - 1] + 1;        } else {            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);        }    }}return dp[S.length][T.length];}

给定一棵有根树，每个节点有权值和价值，路径上的权值为所有节点权值之和，路径的价值为所有节点价值之和。找到根节点到所有其他节点的最大价值路径。

function dfs(node):f[node] = value[node]for child in children[node]:dfs(child)f[node] = max(f[node], f[child] + value[node] - value[child])return f[node]result = dfs(root)

给定面额为d1，d2，...，dn（均为正整数）的硬币，以及一个总金额amount（不小于1），编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果无解，则返回-1。

function coinChange(coins, amount)dp[0] = 0  // 初始状态for i in 1 to amountdp[i] = amount + 1 // 初始值为i，因为最坏情况是每次只能用面额为1的硬币for j in coinsif i >= jdp[i] = min(dp[i], dp[i - j] + 1) // 转移方程if dp[amount] > amountreturn -1  // 无解elsereturn dp[amount]  // 返回最少硬币数

关键词：