基本步骤
一般来说，利用动态规划求解问题可以分为以下几个基本步骤：
- 定义子问题；
- 建立各个子问题之间的递归关系；
- 自底向上求解递归式；
- 组合所有子问题的解从而获得原问题的解；
一维动态规划问题
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
输入：[2, 7, 9, 3, 1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
来源：力扣（LeetCode）
求解问题的步骤：
定义子问题
子问题就是把原问题的规模缩小，例如此题的子问题就是“从前 k 个房子中能偷到的最大金额”，用 f(k) 表示。建立各个子问题之间的递归关系
我们从第 k 间房子开始分析，如果不偷这个房子，那么问题就变成在前 k−1 个房子中偷到最大的金额，也就是子问题 f(k−1)。如果偷这个房子，那么前一个房子不能偷，那么问题就变成在前 k−2 个房子中偷到的最大的金额。两种情况中，选择金额较大的一种结果。
通过分析得到子问题之间的递归关系：f(k) = max{ f(k-1), H(k) + f(k-2) }，H(k)为第 k 间房的金额自底向上求解递归式
自底向上构造一维动态规划表，初始化表为f(0) = 0, f(1) = H(1)，其他的项根据递归关系得出。组合所有子问题的解从而获得原问题的解
此题原问题的解就是动态规划表的最后一项的值。
代码实现：
// 自底向上实现递归策略
function rob(nums: number[]): number[] {
const len: number = nums.length;
if (len === 0) {
return [0];
}
// 子问题：
// f(k) = 偷 [0..k) 房间中的最大金额
// f(0) = 0
// f(1) = nums[0]
// f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }
const dp: Array = new Array(len + 1).fill(0);
// 表格初始化
dp[0] = 0;
dp[1] = nums[0];
for (let k: number = 2; k <= len; k++) {
// 填表
dp[k] = Math.max(dp[k - 1], dp[k - 2] + nums[k - 1]);
}
return dp;
}
复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)
此外如果需要返回到底偷窃了那几家房子，可以根据表的值得到解。
// 回溯得到偷窃的最优解
function trace_back(dp: number[]): number[] {
const res: number[] = new Array();
var i = dp.length - 1;
// 从dp表最后一项开始求解
while (i >= 1) {
// 如果该项大于前一项说明该房间被偷窃
if (dp[i] > dp[i - 1]) {
res.push(i);
i -= 2;
} else {
i -= 1;
}
}
return res.sort((a, b) => a - b);
}
var coins: number[] = [2, 7, 9, 3, 1];
var dp: number[] = rob(coins);
var res: number[] = trace_back(dp);
console.log("动态规划表：", dp);
console.log("偷窃的房间：", res);
测试用例：[2, 7, 9, 3, 1]
输出结果：
二维动态规划问题
最长回文子串
给你一个字符串 s ，找到 s 中最长的回文子串。
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
来源：力扣（LeetCode）
思路
对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 "abcba"，如果我们已经知道 "bcb" 是回文串，那么 "abcba" 一定是回文串，这是因为它的首尾两个字母都是 "a"。也就是说一个字符串是否是回文串，取决于它的首尾两个字符是否相等以及去掉首位两个字符后的子串是否是回文串。这样我们就把原问题分解成了问题规模更小的子问题。
根据这样的思路，我们就可以用动态规划的方法解决本题。
代码实现：
function longestPalindrome(s: string): string {
/*
动态规划求解步骤
1.状态定义：
dp[i][j]为true/false表示s中下标i-j之间的子串是否为回文串
2.状态转移方程
dp[i][j] == (s[i]==s[j] && dp[i+1][j-1])
3.填表并记录最大回文串的长度和起始下标求得解
*/
const len: number = s.length;
if (len < 2) {
return s
}
// 记录最大长度，初始值为1
var maxLen: number = 1;
// 记录最长的回文子串的起始位置
var beginIdx: number = 0;
// 初始化二维数组dp
const dp: boolean[][] = new Array(len).fill(-1).map(() => []);
// for (let i: number = 0; i < len; i++) {
// dp[i] = new Array(len);
// }
// 将对角线上的元素置为true
for (let i: number = 0; i < len; i++) {
dp[i][i] = true;
}
// 填表规则：先一列一列的填写，再一行一行的填，保证左下方的单元格先填
for (let j: number = 1; j < len; j++) {
for (let i: number = 0; i < j; i++) {
if (s[i] !== s[j]) {
dp[i][j] = false;
} else {
// 头尾指针相等时
if (j - i < 3) {
// 如果头尾去掉以后没有字符剩余，或者剩下一个字符的时候，肯定是回文串
dp[i][j] = true;
} else {
// 状态转移
dp[i][j] = dp[i + 1][j - 1];
}
}
// s[i...j]是回文串时判断是否是最长回文子串
if (dp[i][j] && maxLen < j - i + 1) {
maxLen = j - i + 1;
beginIdx = i;
}
}
}
// 根据起始位置和长度返回结果
return s.slice(beginIdx, beginIdx + maxLen);
};
