algorithm - 如何处理当前允许的动作取决于先前完成的动作的动态编程问题？

Question

我开始用制表法解决DP问题，我很好奇如何处理这些问题。例如，这些类型的问题：https://atcoder.jp/contests/dp/tasks/dp_c，http://www.usaco.org/index.php?page=viewproblem2&cpid=574，还有https:// cses.fi/problemset/task/1097. 通常在此类问题的自上而下版本中，将标志传递给下一个函数调用，因此程序知道不重复相同的操作，例如传递一个表示先前选择了活动 0（假期问题）的标志，传递一个表示水已经喝完的标志（水果盛宴问题），传递一个表示轮到谁的标志（移除游戏问题），但在自下而上的版本中这是如何完成的？我不是在寻找这些问题的解决方案，因为我已经完成了这些问题，而是以一种自下而上的方式处理这些问题的一般想法，其中一个动作取决于先前完成的动作，或者一个动作只能是做过一次。先感谢您。

对于那些无法访问链接的人：

链接 1：问题陈述

太郎的暑假明天就要开始了，他已经决定现在就去制定计划。假期由N天组成。对于每个 i (1≤i≤N)，Taro 将选择以下活动之一，并在第 i 天进行： A：在海里游泳。获得ai点的幸福。B：在山里捉虫子。获得双倍的快乐。C：在家做作业。获得幸福的慈分。由于太郎很容易感到无聊，他不能连续两天或更长时间做同样的活动。找出 Taro 获得的最大可能总幸福点。

约束

输入中的所有值都是整数。1≤N≤10 5

1≤a i ,b i ,c i ​ ≤10 4

链接 2：问题陈述

贝西又闯进了农夫约翰的房子！她在厨房里发现了一堆柠檬和一堆橙子（实际上每个都是无限数量的），她决心尽可能多地吃。Bessie 的最大丰满度为 T (1≤T≤5,000,000)。吃橙子增加饱腹感 A，吃柠檬增加饱腹感 B (1≤A,B≤T)。此外，如果她愿意，Bessie 最多可以喝一次水，这会立即使她的饱腹感减少一半（并且会四舍五入）。

帮助 Bessie 确定她可以达到的最大饱腹感！

链接 3：问题陈述

有 n 个数字和两个交替移动的玩家的列表。每走一步，玩家都会从列表中删除第一个或最后一个数字，他们的分数会增加该数字。两名球员都试图最大化他们的分数。当两个玩家都发挥最佳时，第一个玩家的最大可能得分是多少？

约束：

1≤n≤5000

−10^9≤xi≤10^9

标签： algorithmdynamic-programming

Answer 1

（对于问题2和3，我阅读了网上发布的解决方案，并在下面描述了我的理解和代码版本。对于问题1，我没有在网上查找解决方案。）

对于问题 1（Taro 的暑假），我们将活动结束时的状态设为dp[i] = [a, b, c]，其中元组中的每个元素表示如果 Taro 在第 th 天[a, b, c]执行该活动，则获得最多的幸福点。i由于我们不允许连续两天进行同一活动，因此作为活动 X 的每一天的状态取决于前一天的其他两项活动。

dp[0] = [A[0], B[0], C[0]]
dp[i][0] = A[i] + max(dp[i-1][1], dp[i-1][2])
dp[i][1] = B[i] + max(dp[i-1][0], dp[i-1][2])
dp[i][2] = C[i] + max(dp[i-1][0], dp[i-1][1])

function f(ABC){
  const n = ABC.length;
  const dp = [];
  
  dp[0] = ABC[0];
  
  for (let i=1; i<n; i++){
    dp[i] = [0, 0, 0];
    dp[i][0] = ABC[i][0] + Math.max(dp[i-1][1], dp[i-1][2]);
    dp[i][1] = ABC[i][1] + Math.max(dp[i-1][0], dp[i-1][2]);
    dp[i][2] = ABC[i][2] + Math.max(dp[i-1][0], dp[i-1][1]);
  }

  return Math.max(dp[n-1][0], dp[n-1][1], dp[n-1][2])
}

var ABC = [
  [10, 40, 70],
  [20, 50, 80],
  [30, 60, 90]
];

for (row of ABC)
  console.log(String(row));
  
console.log(f(ABC));

---

对于问题 2（Bessie 的丰满度），我们的 dp 状态是二维布尔值，一个用于将丰满度减半之前，一个用于之后dp[i] = [before, after]。dp[i][0]（在将丰满度减半之前）如果我们可以通过添加 A 或 B来达到它是可以实现的。 dp[i/2][1]（在将丰满度减半之后）是可以实现的，如果可以实现的话dp[i][0]。

dp[0] = [true, true]
dp[i][0] = dp[i - A][0] OR dp[i - B][0]
dp[i/2][1] = dp[i][0]

在饱满度减半后再次运行。

dp[i][1] = dp[i - A][1] OR dp[i - B][1]

function f(T, A, B){
  const dp = [];
  
  dp[0] = [true, true];
  
  for (let i=1; i<=T; i++){
    dp[i] = [false, false];
    dp[i][0] ||= i - A >= 0 && dp[i - A][0];
    dp[i][0] ||= i - B >= 0 && dp[i - B][0];
    dp[Math.floor(i/2)][1] = dp[i][0];
  }

  for (let i=0; i<=T; i++){
    dp[i][1] ||= i - A >= 0 && dp[i - A][1];
    dp[i][1] ||= i - B >= 0 && dp[i - B][1];
  }

  for (let i=T; i>=0; i--)
    if (dp[i][1])
      return i;
}

var T = 8;
var A = 5;
var B = 6;

console.log(String([T, A, B]));
console.log(f(T, A, B));

---

对于问题 3（最大化分数），玩家 1 想要最大化score_1 - score_2，玩家 2 想要最小化score_1 - score_2。我们当前间隔的 dp 状态，dp[left][right]描述score_1 - score_2. dp[left][right]当leftequalsright是玩家 1 获得该单个元素的得分时：

dp[i][i] = A[i]

否则，我们考虑如果玩家 1 占据每一边会发生什么。

如果玩家 1 拿下A[l]，我们剩下的就是 interval dp[l + 1][r]，这是玩家 2 可以达到的分数，因为轮到他们了。所以score_1 - score_2将是：

A[l] - dp[l + 1][r]

如果玩家 1 拿下A[r]，那么玩家 2 将获得的分数是dp[l][r - 1]，并且score_1 - score_2将是：

A[r] - dp[l][r - 1]

当然，玩家 1 想要这两个选项中的最大值：

dp[l][r] = max(A[l] - dp[l + 1][r], A[r] - dp[l][r - 1])

function f(A){
  const n = A.length;
  const dp = [];
  let total = 0;

  for (let i=0; i<n; i++){
    dp[i] = new Array(n).fill(0);
    dp[i][i] = A[i];
    total += A[i];
  }

  for (let l=n-2; l>=0; l--)
    for (let r=l+1; r<n; r++)
      dp[l][r] = Math.max(A[l] - dp[l + 1][r], A[r] - dp[l][r - 1]);
  
  // total + difference
  // = (score_1 + score_2) + (score_1 - score_2)
  // = score_1 + score_1
  // return (score_1 + score_1) / 2
  return (total + dp[0][n-1]) / 2;
}

var A = [4, 5, 1, 3];

console.log(String(A));
console.log(f(A));