chapter_dynamic_programming/dp_problem_features/

[giscus[bot]]

chapter_dynamic_programming/dp_problem_features/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_dynamic_programming/dp_problem_features/

[TravelerEntity]

关于子问题是否独立的疑问：
为什么在另外一种关于子问题的描述中，提到

首先，这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。

而在本文中提到

动态规划中的子问题往往不是相互独立的，原问题的解依赖于子问题的解，而子问题的解又依赖于更小的子问题的解。

有点迷惑了。DP 的子问题到底是不是相互独立的呢？

[krahets]

非常好的问题。两个独立性实际上不是同一个概念，它们观察的视角是不同的。

1. 从重叠子问题的角度看，不同的子问题可能依赖相同的更小子问题，这意味着动态规划中子问题“不独立”，或者说“不孤立”。
2. 从最优子结构的角度看，独立性意味着不同子问题的求解之间不应相互影响。

我引用《算法导论》 p383 中的一个例子来介绍 2. 。给定一个图：

A --- B
|     |
C --- D

如果问题是求“从 A 到 D 的最短路径”，记为 $f(A, D)$ ，那么我们可以将问题分解为子问题 $f(A, B)$ 和 $f(B, D)$ ，很明显它们都是可以独立求解的。

而如果转为求“从 A 到 D 的最长路径”，我们会发现：

1. $f(A, B)$ 的解为 $A \rightarrow C \rightarrow D \rightarrow B$ ；
2. 求解 $f(B, D)$ 时不能再使用 $C$ 和 $D$ 了，因为求解 $f(A, B)$ 时已经占用它们了。

这就意味着求最长路径的子问题是“不独立”的，或者说子问题之间的资源不是独立的。

相比于该“独立性”概念，我更喜欢用“无后效性”来描述问题的这种特性。两者的含义在某种意义上是一致的：我们得到一个子问题的解时，需不需要关心它具体是从何而来？

[syutengu]

文科生来回答，这就是自然语言的暧昧性。同一个词语，在不同语境下有不同含义和用法，不能断章取义。

[WhiteRhinos]

所以动态规划是一种特殊的回溯算法吗,回溯算法加上记忆存储优化在改写为循环
用来处理最优和无后效性的题目因为可以通过存储子问题的解来消除回溯的重复子问题计算的缺点

[WhiteRhinos]

看到后面总结了

[WhiteRhinos]

不考虑时间的前提下，所有动态规划问题都可以用回溯（暴力搜索）进行求解

[Rh0-aias]

14.1 和 14.2 章看下来，动态规划给我的感觉更像是解数学题。解决问题的关键是找到「状态转移方程」，也就是递推公式。而代码只是在找到这个递推关系后不断循环递推到问题的解。所以我猜难点其实在如何把问题拆分成子问题来找到这个递推关系。只要找到递推关系后，剩下的工作基本就交给计算机里。而在有约束的情况下，递推关系会变成好几组式子。但只要是线性的关系其实都还好，总可以写成矩阵乘法的形式。 比如图14-9的「状态转移方程」：

dp[i,1]=dp[i-1,2]
dp[i,2]=dp[i-2,1]+dp[i-2,2]

其实等价于：
[DP(i)]=[A][DP(i-1)]+[B][DP(i-2)]
其中[DP(i)]=[dp[i,1],dp[i,2]]^T 是一个1x2的列向量，[A]=[0,0;0,1]和[B]=[1,0;0,1]是两个2x2常数矩阵。
找出[A]和[B]后，不断循环递推到达问题想要的解即可。

而对于非线性的情况下就可能会比较复杂，如果没有办法写成[DP(i)]的次幂形式的话，可能还是得一个个分量来写。
不过我还是不太明白，动态规划里的“动态”，即“dynamic”体现在哪呢？

[Rh0-aias]

另外，“无后效性”好像对应着马可夫过程（Markov process）。

[krahets]

很有趣的问题，可以看下这条 Wiki

The word dynamic was chosen by Bellman to capture the time-varying aspect of the problems, and because it sounded impressive.[11] The word programming referred to the use of the method to find an optimal program, in the sense of a military schedule for training or logistics.

[Rh0-aias]

感恩

[Ryan-BetterMe]

第一个案例的 Swift 版本代码有误：
dp[1] = cost[1]
dp[2] = cost[2]

[ghost]

请问是否可以这样理解后无效性？
后无效性：给定一个确定的状态，该状态的决策 只与 该状态有关，而不受该状态过去所有状态的 影响
若一个问题满足后无效性，当我们得到一个该问题的子问题的解时，就不需要关心它具体是从何而来的

[Tmaof]

原文:
"无后效性是动态规划能够有效解决问题的重要特性之一，定义为：给定一个确定的状态，它的未来发展只与当前状态有关，而与当前状态过去所经历过的所有状态无关。"
有点拗口。
我理解成这样:
"给定一个确定的状态，它未来的状态只与当前状态有关，而与过去所经历的状态无关。"

[RRZXX]

if (n == 1 || n == 2)
return cost[n];

[RRZXX]

这个 逻辑是不是有点问题，n可能是1+1，也可能是2？
if (n == 1)
return cost[n];

if (n == 2) {
return Math.min(costs[1] + costs[1], costs[2]);
}

[RRZXX]

理解错了，没毛病 。
省略了：return Math.min(costs[1] + costs[2], costs[2]);->costs[2]

[gongluck]

为什么初始状态是这样?不理解

[SylvanasQAQ]

 dp[1][1] = 1;   // 一步爬上第一级台阶有一种方法
 dp[1][2] = 0;  // 两步爬上第一级台阶有0种方法
 dp[2][1] = 0;  // 一步爬上第二级台阶有0种方法
 dp[2][2] = 1;  // 两步爬上第二级台阶有一种方法

[jettyyi]

写反了吧，i指的是是第几级台阶，j指的是几步

[ahui-5144]

状态[i,j]表示处在第i阶并且上一轮跳了j阶

    dp[1][1] = 1; 
    dp[1][2] = 0;
    dp[2][1] = 0;
    dp[2][2] = 1

按照定义,dp[1][1]表示处在第 1 阶上并且上一轮跳了 1 阶.但是题目限定不能连续两轮跳 1 阶.那么dp[1][1]应该等于 0 吧.这里不是很理解,求解答

[krahets]

dp[1][1] 代表当前处在第 1 阶，上一轮跳了 1 阶，这个是可行的，因此方案数为 1

[SoftwareEngineerPalace]

重叠子问题、最优子结构、无后效性

[SoftwareEngineerPalace]

dp[2][1] = 0; 为什么是 0，感觉应该是 1 啊

[hpstory]

Hi @SoftwareEngineerPalace , 状态定义为状态[i, j]表示处在第i阶并且上一轮跳了j阶的方案数。dp[2][1]即处在第2阶并且上一轮跳了1阶，又因为题目要求不能连续两轮跳1阶，dp[2][1]不是一个合法方案，所以为0。

[fankaikai]

最后约束爬楼梯这里不太理解：
当上一轮跳了2 阶时，上上一轮可选择跳 1 阶或跳 2阶，dp[i,2]可以从dp[i-2, 1] 或者dp[i-2, 2] 转移而来。
这里为什么是i-2呢？不应该是i-1吗？

[fankaikai]

不好意思，重新理解了一下前面的描述想明白了，上一轮跳2阶对应的是dp[i-2]

[coffee4u]

14.2.1这个不太对啊
如果cost[1]:1, cost[2]:2, cost[3]:5, cost[4]:1,代码从dp0出发，根据min的规则，选择dp1->dp2->dp4,总cost是4。但实际上如果第一轮选择高cost的dp2->dp4, 总cost为3。每次选择min的cost明显不是最优解啊，是我遗漏了什么吗？

[krahets]

建议运行一下代码看看～测试了一下没问题：

输入楼梯的代价列表为 [0, 1, 2, 5, 1]
爬完楼梯的最低代价为 3
爬完楼梯的最低代价为 3

[Danbor86]

dp = [[0] * 3 for _ in range(n + 1)]

大大您好，请问这边为什么是[0]*3而不是[0]*2，谢谢您！

[hpstory]

Hi @Danbor86 ，一般会根据定义的状态多开一些空间，比如dp[n][1]表示处在第n阶并且上一轮跳了1阶。你也可以使用[0]*2，最后的结果就应该是dp[n][0]和dp[n][1]，没有前面的直观。而且有些dp问题会有索引超出范围的情况，这么写也可以减少一些判断逻辑。

[Danbor86]

喔喔！懂了，所以是多开了一些空间但是没有用到对吗？像这样dp这个列表里面子列表中每一个开头元素都是0，但是不用对吗？

[hpstory]

是的，你也可以本地运行一下代码或者使用页面上的可视化，你会发现dp[0]也没有用到

[krahets]

Hi，这个取决于状态定义。

• 原文中的状态定义：状态 [i, j] 表示处在第 i 阶并且上一轮跳了 j 阶，其中 j = 1 or 2 。

由于 j = 1 or 2 ，所以我们要 [0]*3 ，才能有 dp[i][1] 和 dp[i][2] 。

• 你可以改状态定义：状态 [i, j] 表示处在第 i 阶并且上一轮跳了 j+1 阶，其中 j = 0 or 1 。

然后用 [0]*2

[Romantin]

纸质书中的爬楼梯约束问题有错误：
当上一轮跳了2阶时，上上一轮可选择跳1阶或跳2阶，即dp[i,2]可以从dp[i-1,1]或dp[i-1,2]转移过来
这个描述与网页版的不一样。

[krahets]

谢谢指正，！我会尽快修复
应为 即dp[i,2]可以从dp[i-2,1]或dp[i-2,2]转移过来

[ghost]

真是太狗了，佩服的五体投地，为什么可以想出扩展状态，我看着惊掉了我的下巴...,真是应了那句话，在软件工程中，没有什么是加一层解决不了的，如果....那就

[YF-SA]

如果不能那就加上两层~~~~

[perterHUAN]

动态规划中的无后效性一词出自哪里?

查了维基百科和算法导论(第15章)上对于动态规划的描述，都没有发现无后效性一词（可能我看漏了）。

[krahets]

Hi，无后效性在中文版里有：https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92

英文版请见马尔可夫性：https://en.wikipedia.org/wiki/Markov_property

[perterHUAN]

如果一个问题有最优子结构和重叠子问题，那么它就可以使用动态规划的方法来解决。

上面这个断言是正确的吗？如果不是，可以举出反例吗？如果是正确的，那么我们还需要考虑有无后效性的问题吗？

算法导论上只讨论了最优子结构和重叠子问题，并没有说明后效性的问题。这一章节对于重叠子问题的描述较少。对于有无后效性的说明是否有必要呢？

无后效性是动态规划能够有效解决问题的重要特性之一，其定义为：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关。

到底什么是无后效性还是很模糊的概念。

[krahets]

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.

引自 Wiki 的最优子结构定义。最优子结构是一个很“强”的条件，一般来说，问题满足重叠子问题和最优子结构性质，理论上就可以写出状态转移方程，这样我们就可以不断求解更大问题的解了。

相比之下，无后效性就没有那么“绝对”了。如果一个问题不满足无后效性，当前状态的未来发展对其历史路径的依赖非常复杂（例题“爬楼梯与障碍生成”），此时就难以用动态规划解决。但需要注意的是，即使问题第一眼看上去不满足无后效性，我们有时也可以通过扩展状态定义来让问题恢复无后效性（例题“带约束爬楼梯”），从而找到问题的最优子结构。

[adonxx]

约束问题里面一步爬上两阶楼梯不是可以一次爬两阶吗,两次爬两阶应该不行吧,和约束矛盾

[adonxx]

求解答 谢谢

[ztkuaikuai]

约束里面只说了不能连续两轮跳 1 阶，没有说不能连续两轮跳 2 阶，所以说可以连续两次爬两阶

[zhengComing]

如果前面的状态对后面的状态的影响比较复杂，难以直接表示，是不是就意味着需要更复杂的建模方式

[jungleford]

无后效性是动态规划能够有效解决问题的重要特性之一，其定义为：**给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关**。

这不就是马尔可夫链吗 ╮(￣▽￣")╭

[PotatoSmith]

上强度了

[syutengu]

不允许连跳两次1阶这题，初始状态设置是这样理解的吧：

    const dp = [
      /* [无用仅占位, 跳1阶到此的解数, 跳2阶到此的解数] */
      [null, null, null],//0阶解，无用仅占位
      [null, 1, 0],//1阶解 = 跳1阶可达 + 跳2阶不可达
      [null, 0, 1],//2阶解 = 跳1阶可达但违规（因为此时前一次只能也是跳1阶） + 跳2阶可达
    ]

因此，以后的状态设置：

      dp[i] = [
        null,
        dp[i - 1][2],
        dp[i - 2][1] + dp[i - 2][2]
      ]

[syutengu]

2i屏障这题，只观察到以下：

1. 所有的大于1的奇数台阶，都必被经过；
2. 基于1. ，当n等于大于1的奇数的2倍时，都是0解； e.g., n=6,10,14,18

[pplam]

不能连续两轮跳一阶的问题，状态转移方程也可以是 dp[i] = dp[i-2] + dp[i-3]，因此另外一个解法可以是：

def climbing_stairs_constraint_dp(n: int) -> int:
    dp = [0, 1, 1, 2]
    if n <= 3:
        return dp[n]
    for i in range(4, n+1):
        dp[1], dp[2], dp[3] = dp[2], dp[3], dp[1] + dp[2]
    return dp[3]

[syutengu]

"最小成本爬楼梯"对应lc#746. Min Cost Climbing Stairs，有一个经典的歧义。
"到达顶部(reach the top of the floor)"可以理解为"到达i阶"，也可以理解为"超越i阶"。
或者说，各阶的成本，到底是"门票（入場券、买了才能进）"还是"车票（乗車券、买了才能走）"。
两种不同的理解，解法和答案都会产生差异。不知道理解是否有误？
e.g., [10,15,20,25,30,35,40]

/* DP 超越i阶 */
function minCostClimbingStairs(cost) {
  const dp = [0, 0]
  for (let i = 2; i <= cost.length; i++) {
    /* dp[i]定义：超过i级台阶（i级台阶本身不一定被踩到）所需最小成本 */
    dp[i] = Math.min(
      dp[i - 2] + cost[i - 2],
      dp[i - 1] + cost[i - 1],
    )
  }
  console.log(dp) //[0,0,10,15,30,40,60,75]
  return dp.at(-1) //75
}

/* DP 到达i阶 */
function min_cost_climbing_stairs_dp(cost) {
  const dp = [0, cost[0], cost[1]]
  for (let i = 3; i < cost.length; i++) {
    // 设 dp[i] 为爬到第i阶累计付出的代价（包含第i阶本身，即第i阶必须被"踩到"），
    // 由于第i阶只可能从i-1阶或i-2阶走来，
    // 因此 dp[i] 只可能等于 dp[i-1]+cost[i] 或 dp[i-2]+cost[i] 。
    dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]
    /* 最优子结构的含义：原问题的最优解是从子问题的最优解构建得来的。 */
  }
  console.log(dp)//[0,10,15,35,45,70,85]
  return dp.at(-1)//85
}

[syutengu]

按照lc#746的说明，
“Once you pay the cost, you can either climb one or two steps.”，
即成本是车票（支付才能离开第i阶），
那么就是"超越i阶"问题。

而这里的表述"在第i个台阶需要付出的代价",
根据解法反推，应该成本是"门票"（支付才能踩上第i阶），
那么就是“到达i阶”问题。