动态规划求解最优店铺访问问题：状态计算疑问求助

嘿，你已经开了个好头！我来帮你把这个问题的动态规划思路理得明明白白，一步步拆解每个状态的计算逻辑，你就能轻松搞定后续的步骤啦。

首先先明确我们的状态定义（你写的P应该是笔误，我统一用题目里的V来表述）：

• V(0,i)：前i家店铺不访问第i家时的最大收益
• V(1,i)：前i家店铺访问第i家时的最大收益

再确认下输入的数组对应关系（按你说的非0索引）：

核心转移方程 #

首先我们需要定义虚拟的初始状态（第0家店铺，不存在）：

• V(0,0) = 0：不访问虚拟店铺，收益为0
• V(1,0) = -∞：虚拟店铺无法访问，收益为负无穷（表示不可能的情况）

然后是两个核心转移逻辑：

1. 不访问第i家店：此时前i家的最大收益就是前i-1家店的最大收益（不管前i-1家最后有没有访问）

   V(0,i) = max(V(0,i-1), V(1,i-1))
   

2. 访问第i家店：根据题目描述，访问第i家店时，无法访问前run_cost[i]家店（比如访问第3家时，run_cost=2，无法访问前2家）。也就是说，我们只能从第i - run_cost[i] - 1家店及之前的状态里取最大收益，再加上当前店铺的价值：

   # 先计算可以回溯到的最远店铺j
   j = i - run_cost[i] - 1
   # 如果j >=0，取前j家的最大收益；否则取0（相当于从虚拟第0家开始）
   prev_max = max(V(0,j), V(1,j)) if j >=0 else 0
   V(1,i) = store_value[i] + prev_max
   

逐个计算i=1到6的状态 #

现在我们一步步算每个i的结果：

i=1

• V(0,1) = max(V(0,0), V(1,0)) = max(0, -∞) = 0 ✔️ 和你算的一致
• j = 1 - 0 -1 =0，prev_max = max(0, -∞)=0，所以V(1,1)=2+0=2 ✔️ 和你算的一致

i=2

• V(0,2)=max(V(0,1), V(1,1))=max(0,2)=2
• j=2-1-1=0，prev_max=0，所以V(1,2)=4+0=4

i=3

• V(0,3)=max(V(0,2), V(1,2))=max(2,4)=4
• j=3-2-1=0，prev_max=0，所以V(1,3)=9+0=9（符合题目里“无法访问前2家”的设定，只能从虚拟店铺开始）

i=4

• V(0,4)=max(V(0,3), V(1,3))=max(4,9)=9
• j=4-3-1=0，prev_max=0，所以V(1,4)=1+0=1（run_cost=3，无法访问前3家，只能从虚拟店铺开始）

i=5

• V(0,5)=max(V(0,4), V(1,4))=max(9,1)=9
• j=5-1-1=3，prev_max=max(V(0,3), V(1,3))=max(4,9)=9，所以V(1,5)=4+9=13（run_cost=1，无法访问第4家，所以取前3家的最大收益）

i=6

• V(0,6)=max(V(0,5), V(1,5))=max(9,13)=13
• j=6-2-1=3，prev_max=max(V(0,3), V(1,3))=9，所以V(1,6)=2+9=11（run_cost=2，无法访问第4、5家，取前3家的最大收益）

最终结果 #

前6家店铺的最大收益就是max(V(0,6), V(1,6))=max(13,11)=13。

内容的提问来源于stack exchange，提问作者algofunrasmus