DP笔记(2)：线性DP之单线性，爬楼梯、打家劫舍、2键/4键键盘
Date：
线性动态规划简介
线性动态规划：具有「线性」阶段划分的动态规划方法统称为线性动态规划（简称为「线性 DP」），如下图所示。
如果状态包含多个维度，但是每个维度上都是线性划分的阶段，也属于线性 DP。比如背包问题、区间 DP、数位 DP 等都属于线性 DP。
线性 DP 问题的划分方法有多种方式。
如果按照「状态的维度数」进行分类，我们可以将线性 DP 问题分为：
一维线性 DP 问题
二维线性 DP 问题
多维线性 DP 问题
如果按照「问题的输入格式」进行分类，我们可以将线性 DP 问题分为：
单串线性 DP 问题
双串线性 DP 问题
矩阵线性 DP 问题
无串线性 DP 问题
本文中，我们将按照问题的输入格式进行分类，对线性 DP 问题中各种类型问题进行一一讲解。
单串线性 DP 问题
单串线性 DP 问题：问题的输入为单个数组或单个字符串的线性 DP 问题。状态一般可定义为dp[i]，表示为：
「以数组中第i 个位置元素 nums[i] 为结尾的子数组（nums[0]...nums[i]）」的相关解。
「以数组中第 i−1 个位置元素nums[i−1] 为结尾的子数组（nums[0]...nums[i−1]）」的相关解。
「以数组中前 i 个元素为子数组（nums[0]...nums[i−1]）」的相关解。
这 33种状态的定义区别在于相差一个元素nums[i]。
第 1 种状态：子数组的长度为 i+1，子数组长度不可为空；
第 22种状态、第 3 种状态：这两种状态描述是相同的。子数组的长度为i，子数组长度可为空。在i=0 时，方便用于表示空数组（以数组中前 0 个元素为子数组）。
双串线性 DP 问题
双串线性 DP 问题：问题的输入为两个数组或两个字符串的线性 DP 问题。状态一般可定义为dp[i][j]，表示为：
「以第一个数组中第i 个位置元素 nums1[i] 为结尾的子数组（nums1[0]...nums1[i]）」与「以第二个数组中第 j 个位置元素 nums2[j] 为结尾的子数组（nums2[0]...nums2[j]）」的相关解。
「以第一个数组中第 i−1 个位置元素 nums1[i−1] 为结尾的子数组（nums1[0]...nums1[i−1]）」与「以第二个数组中第 j−1 个位置元素 nums2[j−1] 为结尾的子数组（nums2[0]...nums2[j−1]）」的相关解。
「以第一个数组中前 i 个元素为子数组（nums1[0]...nums1[i−1]）」与「以第二个数组中前 j 个元素为子数组（nums2[0]...nums2[j−1]）」的相关解。
这 33 种状态的定义区别在于相差一个元素 nums1[i] 或 nums2[j]。
第 11 种状态：子数组的长度为 i+1 或 j+1，子数组长度不可为空
第 22 种状态、第 33 种状态：子数组的长度为 i 或 j，子数组长度可为空。i=0 或j=0 时，方便用于表示空数组（以数组中前 00 个元素为子数组）。
矩阵线性 DP问题
矩阵线性 DP 问题：问题的输入为二维矩阵的线性 DP 问题。状态一般可定义为 dp[i][j]，表示为：从「位置 (0,0)(0,0)」到达「位置 (i,j)」的相关解。
无串线性 DP 问题
无串线性 DP 问题：问题的输入不是显式的数组或字符串，但依然可分解为若干子问题的线性 DP 问题。
线性动态规划题目
爬楼梯合集
爬楼梯 https://leetcode.cn/problems/climbing-stairs/description/
使用最小花费爬楼梯 https://leetcode.cn/problems/min-cost-climbing-stairs/description/
爬楼梯
这道题目算得上最简单的动态规划类的题目了
爬楼梯解法
步骤一：定义子问题
我们来一个一个分析一下：
当只有 1 阶台阶时，你只有一种方式爬到顶端
当只有 2 阶台阶时，你有两种方式，如示例1所示
当只有 3 阶台阶时，你有三种方式，如示例2所示
分析到这里的时候，看看这几个数据，我有一个大胆的猜测，当只有 4 阶台阶时，可以有 爬到第2阶台阶所需要的方法数 加上 爬到第3阶台阶所需要的方法数 种方法数，为什么这么说呢？你想想，要想爬到第4阶台阶，你只能是从第3阶或者第2阶台阶爬上来的，只有这两种方式对吧，所以：
4阶方法总数 = 3阶方法总数 + 2阶方法总数 ……
再看是否存在 存在重复子问题，其实爬楼梯和斐波那契数列类似，最终的状态转移方程是一样的，所以显然存在重复子问题。当然直观来看也容易分析出，10 阶台阶的爬法包含了 8、9 阶的爬法，而 9 阶台阶爬法包含了 8 阶的，所以存在重复子问题。
定义子问题：
我们可以将到达第 n 阶台阶的方法看作一个子问题，记为 f(n)。显然，到达第 1 阶台阶的方法只有一种，就是从第 0 阶台阶走 1 阶台阶，即 f(1) = 1。到达第 2 阶台阶的方法有两种，可以从第 1 阶台阶走 1 阶台阶，也可以从第 0 阶台阶直接走 2 阶台阶，即 f(2) = f(1) + f(0) = 2。
步骤二：写出子问题的递推关系
根据上述分析，我们可以得出以下递推关系：f(n) = f(n-1) + f(n-2)
步骤三：确定 DP 数组的计算顺序
根据递推关系，我们可以从下往上计算 DP 数组，即先计算 f(1) 和 f(2)，再计算 f(3)、f(4)，以此类推。
所以爬楼梯的状态转移方程为：
dp(i) = dp(i-1) + dp(i-2)
dp(1) = 1
dp(2) = 2
步骤四：空间优化（可选）
由于递推关系只涉及到前两个子问题的解，因此我们可以使用两个变量来存储前两个子问题的解，从而避免使用 DP 数组。具体来说，我们可以定义两个变量 pre 和 cur，分别表示到达第 n-1 阶台阶的方法数和到达第 n 阶台阶的方法数。初始状态为 pre = 1，cur = 2。然后，我们可以迭代计算 cur 的值，每次迭代将 cur 的值赋给 pre，并重新计算 cur 的值。
爬楼梯代码实现
字问题递归表述
function dp(i) {
switch (i) {
case 1:
return 1;
case 2:
return 2;
default:
return dp(i - 1) + dp(i - 2);
}
}这样写重复计算了子结构，所以我们不要每次傻傻的执行 dp(i - 1)（因为这样计算了超多重复子问题），我们需要用缓存兜底：
递归改为迭代
function climbStairs(n) {
if (n <= 1) return 1;
let dp = new Array(n + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}空间优化
function climbStairs(n) {
if (n <= 1) return 1;
let prev1 = 1, prev2 = 1; // 用两个变量来存储前两个状态
for (let i = 2; i <= n; i++) {// 迭代计算每一级的方法数
let curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;// 返回最后的状态
}使用最小花费爬楼梯
使用最小花费爬楼梯解法
这里忽略详细的推导过程
问题分析
到达第i级台阶的阶梯顶部的最小花费，有两个选择：
先付出最小总花费minCost[i-1]到达第i级台阶（即第i-1级台阶的阶梯顶部），踏上第i级台阶需要再花费cost[i]，再迈一步到达第i级台阶的阶梯顶部，最小总花费为minCost[i-1] + cost[i])；
先付出最小总花费minCost[i-2]到达第i-1级台阶（即第i-2级台阶的阶梯顶部），踏上第i-1级台阶需要再花费cost[i-1]，再迈两步跨过第i级台阶直接到达第i级台阶的阶梯顶部，最小总花费为minCost[i-2] + cost[i-1])；
则minCost[i]是上面这两个最小总花费中的最小值。
minCost[i] = min(minCost[i-1] + cost[i], minCost[i-2] + cost[i-1])。
最小总花费的初始值为：
第0级台阶： minCost[0] = min(cost[-1], cost[0]) = min(0, cost[0]) = 0，
第1级台阶： minCost[1] = min(cost[0], cost[1])。
第i级台阶： minCost[i] = min(minCost[i-1] + cost[i], minCost[i-2] + cost[i-1])。
步骤二：写出子问题的递推关系
为了爬到第 n 级台阶，你可以从第 n-1 级或者第 n-2 级台阶跨一步或两步上来，因此：
f(n)=min(f(n−1)+cost[n−1],f(n−2)+cost[n−2])
步骤三：确定 DP 数组的计算顺序
我们使用动态规划数组来解决这个问题。从底向上计算，避免重复计算子问题。
确定边界条件：
f(0) = 0：因为你可以从地面开始爬，不需要任何费用。
f(1) = 0：类似地，第一步可以是从地面直接跨到第一级，不需要任何费用。
递推计算：
对于 n >= 2，按照递推公式 f(n) = min(f(n-1) + cost[n-1], f(n-2) + cost[n-2]) 进行计算。
使用最小花费爬楼梯代码
使用 DP 数组的实现
function minCostClimbingStairs(cost) {
const n = cost.length;
if (n === 0) return 0;
if (n === 1) return cost[0];
let dp = new Array(n + 1);
dp[0] = 0;
dp[1] = 0;
for (let i = 2; i <= n; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}空间优化后的实现
我们注意到每次计算 f(n) 只需要 f(n-1) 和 f(n-2)，因此可以用两个变量代替整个数组，从而优化空间复杂度到 O(1)。
function minCostClimbingStairs(cost) {
const n = cost.length;
if (n === 0) return 0;
if (n === 1) return cost[0];
let prev1 = 0;
let prev2 = 0;
for (let i = 2; i <= n; i++) {
let curr = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}打家劫舍合集
打家劫舍共4道题，1,2,4 题难度依次变大，3题为树结构。
https://leetcode.cn/problems/house-robber/
https://leetcode.cn/problems/house-robber-ii/description/
https://leetcode.cn/problems/house-robber-iv/description/
https://leetcode.cn/problems/house-robber-iii/description/
打家劫舍I求解
步骤一：定义子问题
f(k)表示从前面k个房子能获取的最大金额；
原问题要能由子问题表示。例如这道小偷问题中，k=n 时实际上就是原问题；
一个子问题的解要能通过其他子问题的解求出。例如本题：f(k) 可以由 f(k-1)和 f(k-2)求出，具体原理后面会解释。这个性质就是所说的"最优子结构"。如果定义不出这样的子问题，那么这道题实际上没法用动态规划解。
步骤二：写出子问题的递推关系
每个房子的金额用H表示，那么k个房子有两种偷发，如上图所示。容易得出递推公式（重要）：
注意这里涉及到边界值：
k=0时，f(0)=0
k=1时，f(1)=H0
步骤三：确定 DP 数组的计算顺序
那么，既然 DP 数组中的依赖关系都是向右指的，DP 数组的计算顺序就是从左向右。这样我们可以保证，计算一个子问题的时候，它所依赖的那些子问题已经计算出来了。
确定了 DP 数组的计算顺序之后，我们就可以写出题解代码了：见3.3的代码一。
步骤四：空间优化（可选）
最后一步计算 f(n) 的时候，实际上只用到了 f(n-1)和 f(n-2) 的结果。那么只用两个变量保存两个子问题的结果，就可以依次计算出所有的子问题。下面的图比较了空间优化前和优化后的对比关系，代码见3.3代码二：
打家劫舍I代码
对于连续的 nnn 栋房子：H 1 ,H 2 ,H 3 ......H n H~1~,H~2~,H~3~......H~n~H 1 ,H 2 ,H 3 ......H n ，小偷挑选要偷的房子，且不能偷相邻的两栋房子，方案无非两种：
方案一：挑选的房子中包含最后一栋；
方案二：挑选的房子中不包含最后一栋；
获得的最大收益的最终方案，一定在这两种方案中产生，用代码表述就是：
最优结果 = Math.max(方案一最优结果，方案二最优结果)
子问题的递归表述
var robTo = function (nums, lastIndex) {
if (lastIndex === 0) return nums[0];
// 方案一，包含最后一栋房子，则应该丢弃倒数第二栋房子
let sum1 = robTo(nums, lastIndex - 2) + nums[lastIndex];
// 方案二，不包含最后一栋房子，那么方案二的结果就是到偷到 lastIndex-1 为止的最优结果
let sum2 = robTo(nums, lastIndex - 1);
return Math.max(sum1, sum2);
};将问题表述成最优子问题的解后，这个问题就解决了：
var rob = function(nums) {
return robTo(nums, nums.length - 1);
};递归转迭代
到上一步为止，该问题就已经解决了。但是递归的方式性能太差，中间有太多重复的计算，所以还需要最后一步：将 自顶向下 的递归，转化成 自底向上 的迭代。
var rob = function(nums) {
const len = nums.length;
if(len == 0) return 0;
const dp = new Array(len + 1);
dp[0] = 0;
dp[1] = nums[0];
for(let i = 2; i <= len; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
}
return dp[len];
};空间优化
使用两个变量取代数组。
var rob = function(nums) {
if (nums.length === 0) {
return 0;
}
if (nums.length === 1) {
return nums[0];
}
// 仍然用两个变量来存储方案一和方案二的最优结果
// 不同的是，这次从0开始，lastIndex 取最小值 1
let sum1 = nums[0];
let sum2 = nums[1];
// 然后通过迭代不断增大 lastIndex，过程中维护新的sum1，sum2，直到数组末尾
for (let lastIndex=2; lastIndex<nums.length; lastIndex++) {
let tmp = sum1;
// 此时的方案一就是上一步中的方案二，
// 但要求的是最优解，所以要判断前一步的 sum1 和 sum2 哪个更大
if (sum2 > sum1) {
sum1 = sum2;
}
// sum2 是包含最后一栋房子的方案，
// 每向后增加一栋房子，就是前一步的 sum1（不包含 lastIndex - 1 ）
// 加上当前 lastIndex 栋房子的金钱
sum2 = tmp + nums[lastIndex];
}
return sum1 > sum2 ? sum1 : sum2;
};打家劫舍 II代码
这道题目和198.打家劫舍 (opens new window)是差不多的，唯一区别就是成环了。
对于一个数组，成环的话主要有如下三种情况：
情况一：考虑不包含首尾元素
情况二：考虑包含首元素，不包含尾元素
情况三：考虑包含尾元素，不包含首元素
注意我这里用的是"考虑"，例如情况三，虽然是考虑包含尾元素，但不一定要选尾部元素！ 对于情况三，取nums[1] 和 nums[3]就是最大的。
而情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了。
分析到这里，本题其实比较简单了。 剩下的和198.打家劫舍 (opens new window)就是一样的了。
var rob = function (nums) {
const len = nums.length;
if (len == 0) return 0;
if (len == 1) return nums[0];
const result1 = robRange(nums, 0, len - 2);
const result2 = robRange(nums, 1, len - 1);
return Math.max(result1, result2);
};
function robRange(nums, start, end) {
if (end === start) return nums[start];
const n = end + 1;
const dp = new Array(n);
dp[start] = 0;
dp[start + 1] = nums[start];
for (let i = start + 2; i <= n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[n];
}这个代码是为了保持和打家劫舍1 保持一致。也可以这样写：https://programmercarl.com/0213.打家劫舍II.html
2键/4键键盘
四键键盘
假设你有一个特殊的键盘包含下面的按键：
Key 1: (A)：在屏幕上打印一个 'A'。
Key 2: (Ctrl-A)：选中整个屏幕。
Key 3: (Ctrl-C)：复制选中区域到缓冲区。
Key 4: (Ctrl-V)：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。
现在，你只可以按键 N 次（使用上述四种按键），请问屏幕上最多可以显示几个 'A'呢？
样例 1: 输入: N = 3 输出: 3 解释: 我们最多可以在屏幕上显示三个'A'通过如下顺序按键： A, A, A
样例 2: 输入: N = 7 输出: 9 解释: 我们最多可以在屏幕上显示九个'A'通过如下顺序按键： A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
如何在 N 次敲击按钮后得到最多的 A？我们穷举呗，对于每次按键，我们可以穷举四种可能，很明显就是一个动态规划问题。
第一种思路
这种思路会很容易理解，但是效率并不高，我们直接走流程：对于动态规划问题，首先要明白有哪些「状态」，有哪些「选择」。
具体到这个问题，对于每次敲击按键，有哪些「选择」是很明显的：4 种！就是题目中提到的四个按键：A、Ctrl-A（C-A）、Ctrl-C（C-C）、和Ctrl-V（C-V）。
接下来，思考一下对于这个问题有哪些「状态」？或者换句话说，我们需要知道什么信息，才能将原问题分解为规模更小的子问题？
你看我这样定义三个状态行不行：
剩余的按键次数，用n表示；
当前屏幕上字符 A 的数量，用a_num表示；
剪切板中字符 A 的数量，用copy表示。
如此定义「状态」，就可以知道 base case：当按键次数用完时（即 n 为0），屏幕上字符A的数量（即 a_num）就是我们想要的答案。
结合刚才说的 4 种「选择」，我们可以把这几种选择通过状态转移表示出来：
状态转移：
根据每种按键操作，我们可以将状态转移表示出来：
按下A键：增加一个字符A，同时消耗1次按键次数。
新状态：dp(n - 1, a_num + 1, copy)
按下Ctrl-V(C-V)键：将剪切板中的字符A粘贴到屏幕上，同时消耗1次按键次数。
新状态：dp(n - 1, a_num + copy, copy)
按下Ctrl-A（C-A）和Ctrl-C（C-C）：全选并复制屏幕上的字符A到剪切板，同时消耗2次按键次数。
新状态：dp(n - 2, a_num, a_num)
这样可以看到问题的规模n在不断减小，肯定可以到达n = 0的 base case，所以这个思路是正确的：
function maxA(n) {
const memo = new Map();
function dp(n, a_num, copy) {
if (n <= 0) return a_num;
const key = `${n},${a_num},${copy}`;
if (memo.has(key)) return memo.get(key);
const pressA = dp(n - 1, a_num + 1, copy);
const pressCV = dp(n - 1, a_num + copy, copy);
const pressCA_CC = n > 1 ? dp(n - 2, a_num, a_num) : 0;
const result = Math.max(pressA, pressCV, pressCA_CC);
memo.set(key, result);
return result;
}
return dp(n, 0, 0);
}在这个代码中，我们使用一个递归函数 dp 来计算在剩余 n 次按键下，最大可能的字符A数量。我们用一个 memo（记忆化存储）来避免重复计算。
n 是一个明确的变量，最多为 N，但是 a_num 和 copy 可以在理论上达到非常高的值，这导致状态空间变得非常大，从而使得算法的复杂度非常高，可能会达到 O(N^3 ) 甚至更高。
为了改进这个算法，我们需要重新定义状态，以便减少状态空间和优化时间复杂度。我们可以通过将状态定义得更加抽象，专注于每一步操作时的选择和影响，从而简化问题。
第二种思路
这种思路稍微有点复杂，但是效率高。继续走流程，「选择」还是那 4 个，但是这次我们只定义一个「状态」，也就是剩余的敲击次数n。
这个算法基于这样一个事实，最优按键序列一定只有两种情况：
要么一直按A：A,A,…A（当 N 比较小时）。
要么是这么一个形式：A,A,…C-A,C-C,C-V,C-V,…C-V（当 N 比较大时）。
因为字符数量少（N 比较小）时，C-A C-C C-V这一套操作的代价相对比较高，可能不如一个个按A；而当 N 比较大时，后期C-V的收获肯定很大。这种情况下整个操作序列大致是：开头连按几个A，然后C-A C-C组合再接若干C-V，然后再C-A C-C接着若干C-V，循环下去。
换句话说，最后一次按键要么是A要么是C-V。明确了这一点，可以通过这两种情况来设计算法：
int[] dp = new int[N + 1]; // 定义：dp[i] 表示 i 次操作后最多能显示多少个 A for (int i = 0; i <= N; i++) dp[i] = max( 这次按 A 键， 这次按 C-V )
对于「按A键」这种情况，就是状态i - 1的屏幕上新增了一个 A 而已，很容易得到结果：
// 按 A 键，就比上次多一个 A 而已 dp[i] = dp[i - 1] + 1;
刚才说了，最优的操作序列一定是C-A C-C接着若干C-V，所以我们用一个变量j作为若干C-V的起点。那么j之前的 2 个操作就应该是C-A C-C了：
function maxA(N) {
const dp = Array(N + 1).fill(0); // dp[0] = 0;
for (let i = 1; i <= N; i++) {
dp[i] = dp[i - 1] + 1;// 按下A键
for (let j = 2; j < i; j++) { // 按下C-A C-C组合和若干次C-V键
// 全选&复制 dp[j-2]，连续粘贴i-j次 屏幕上共 dp[j-2]*(i-j+1)个 A
dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
}
}
return dp[N];
}其中j变量减 2 是给C-A C-C留下操作数，看个图就明白了：
这样，此算法就完成了，时间复杂度 O(N^2)，空间复杂度 O(N)，这种解法应该是比较高效的了。
总结：
动态规划难就难在寻找状态转移，不同的定义可以产生不同的状态转移逻辑，虽然最后都能得到正确的结果，但是效率可能有巨大的差异。
回顾第一种解法，重叠子问题已经消除了，但是效率还是低，到底低在哪里呢？抽象出递归框架：
def dp(n, a_num, copy): dp(n - 1, a_num + 1, copy), # A dp(n - 1, a_num + copy, copy), # C-V dp(n - 2, a_num, a_num) # C-A C-C
看这个穷举逻辑，是有可能出现这样的操作序列C-A C-C，C-A C-C...或者C-V,C-V,...。显然这种操作序列的结果不是最优的，但是我们并没有想办法规避这些情况的发生，从而增加了很多没必要的子问题计算。
回顾第二种解法，我们稍加思考，发现最优的序列应该是这种形式：A,A..C-A,C-C,C-V,C-V..C-A,C-C,C-V..。
根据这个事实，我们重新定义了状态，重新寻找了状态转移，从逻辑上减少了无效的子问题个数，从而提高了算法的效率。
两个键的键盘
最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：
Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
Paste（粘贴）：粘贴 上一次 复制的字符。
给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。
示例 1：输入：3 输出：3
解释： 最初, 只有一个字符 'A'。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 'AA'。
第 3 步, 使用 Paste 操作来获得 'AAA'。
示例 2：输入：n = 1 输出：0
对于一个数n，他需要进行多少次的复制全部和粘贴的操作，比如25个A，最大能被25整除（比25小的数中）的数是5，那么我需要复制5个A粘贴5次就可以得到25个A，那么怎么得到5个A，最大能被5整除（比5小的数中）的数是1，因此只能通过复制一个A并粘贴5次。
当n = 1时，已经有一个A了，我们不需要其他操作，返回0
当n = 2时，我们需要复制一次，粘贴一次，返回2
当n = 3时，我们需要复制一次，粘贴两次，返回3
当n = 4时，这就有两种做法，一种是我们需要复制一次，粘贴三次，共4步，另一种是先复制一次，粘贴一次，得到AA，然后再复制一次，粘贴一次，得到AAAA，两种方法都是返回4
当n = 5时，我们需要复制一次，粘贴四次，返回5
当n = 6时，我们需要复制一次，粘贴两次，得到AAA，再复制一次，粘贴一次，得到AAAAAA，共5步，返回5
可以看出对于n，至多需要n步，即cppppp....，而如果可以分解成相同的几份，则可以减少次数，比如n=6时，目标是AAAAAA，可以分解为两个AAA或者三个AA
假设 n%m=0,n/m=min_val; m的范围[1,n-1]（总共需要输出n个A，一次复制M个，最小粘贴min_val次）
那么动态转移方程为：
dp[n]=dp[m]+（min_val-1）+1;
dp[m]代表要得到m个A最少需要多少次操作；
min_val-1代表需要对m个A进行粘贴的次数；
最后+1是复制m个A的次数。
function minSteps(n) {
const dp = new Array(n + 1).fill(0); // 创建一个长度为 n+1 的数组 dp，初始化所有元素为 0
dp[1] = 0; // dp[1] 初始化为 0，因为已经有一个 'A'
for (let i = 2; i <= n; ++i) {
let min_val = Infinity; // 初始化最小粘贴次数为无穷大
let index;
for (let j = i - 1; j >= 1; --j) {// 找出最大的能被 i 整除的 j
if (i % j === 0) {
let val = i / j;
if (val < min_val) {
min_val = val; // 最少的粘贴次数
index = j; // 在哪个位置粘贴
}
}
}
dp[i] = dp[index] + min_val - 1 + 1;// 更新 dp[i]
}
return dp[n];// 找出最大的能被 i 整除的 j
}这个如果你没有看明白。那么，为了简化问题，我们可以反过来思考：
假设我们已经有 i 个 'A'，如何获得这些 'A' 是通过一些 j 个 'A' 复制若干次得到的。
因此，我们需要找到一个 j，使得 j 个 'A' 通过粘贴操作能得到 i 个 'A'，即 i % j == 0。
更具体地：如果 i 能被 j 整除（即 i % j == 0），说明可以通过先获得 j 个 'A'，然后粘贴若干次（具体是 i / j 次）得到 i 个 'A'。
例如，假设我们要得到 i = 16 个 'A'：
我们可以通过先获得 8 个 'A'，然后粘贴一次得到 16 个 'A'。操作步骤是：
先获得 8 个 'A' 的操作次数是 dp[8]。
再粘贴一次得到 16 个 'A'，总操作次数是 dp[8] + 1。
而要获得 8 个 'A'，可以先获得 4 个 'A' 然后粘贴一次，操作次数是 dp[4] + 1。
获得 4 个 'A' 是通过先获得 2 个 'A' 然后粘贴一次，操作次数是 dp[2] + 1。
获得 2 个 'A' 是通过先获得 1 个 'A' 然后粘贴一次，操作次数是 dp[1] + 1。
通过这种方式递归地计算，我们可以找到最优的操作次数。
状态转移方程
dp[i] 表示获得 i 个 'A' 的最小操作次数。那么：
对于每个 i，我们要找到最大的 j（1 <= j < i），使得 i % j == 0。
一旦找到这个 j，可以通过 dp[j] 的操作次数，再加上从 j 到 i 的粘贴次数，即 i / j - 1 次粘贴操作（注意第一次的“复制”操作，所以加 1），总操作次数为 dp[j] + i / j。
标准动态规划代码：
function minSteps(n) {
if (n == 1) return 0;
// 对每一个格子，如果i可以被j除尽，说明j个A可以通过复制粘贴得到i个A，复制粘贴次数为i / j。
let dp = new Array(n + 1).fill(0);//到i第个A的最小操作次数
dp[1] = 0;// dp[1] 初始化为 0，因为已经有一个 'A'，1个A 不需要复制
for (let i = 2; i <= n; ++i) {// 对于每个 i 从 2 到 n，找到最大的能被 i 整除的 j，并更新 dp[i]。
for (let j = 1; j <= i / 2; ++j) {// 找出最大的能被 i 整除的 j
if (i % j == 0) {//找到可以整除的因子
dp[i] = Math.min(dp[i], dp[j] + (i / j));//状态转移
}
}
}
return dp[n];
}参考文章：
第九章动态规划——使用最小花费爬楼梯 https://blog.csdn.net/DDDDWJDDDD/article/details/137244557
650.只有两个键的键盘（动态规划） https://blog.csdn.net/Linke66/article/details/120384747
Leetcode [650] 只有两个键的键盘 & Leetcode [651] 四键键盘 动态规划 https://www.cnblogs.com/zl1991/p/14742514.html
转载本站文章《DP笔记(2)：线性DP之单线性，爬楼梯、打家劫舍、2键/4键键盘》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9109.html