<p>定义dp_i表示第i个座位坐不坐人，前i个座位的安排数量，然后就xjb转移🐶</p>

<p>有原题描述么，观众数是数组长度个？</p>

我连第一步的状态都确定不了，标记下看看有没大佬点拨下。

dpij，表示已经坐了i个人，最后一个人在j这个位置，状态数nm，每次转移是一个前缀和，所以是常数转移。

<p>md刷一下午力扣了，来虎扑又是这？</p>

<p>dp（i）表示前i个座位有多少种方法，然后按第i位坐不坐人讨论，不坐人是dp（i-1），坐人了假设j位置和i位置距离大于等于6，综合一下转移公式为dp（i）=dp（i-1）+dp（j）</p>

<p>你先说说这为啥要动态规划...一次遍利贪心不就过去了吗</p>

<div data-type="normal">来了来了，编辑了一下，po了原题。</div><div data-type="normal">观众数是个变量，有n个座位，可以有0到n个观众。</div>

<p>例子太少，验证不了是不是完全对</p><p><img src="https://i1.hoopchina.com.cn/hupuapp/bbs/81101878877212/thread_81101878877212_20200927040712_s_98003_o_w_812_h_517_41396.jpg"/></p>

位置按1到n编号，dp[i]表示最后一个人坐在位置i时的方法总数。<br>初始状态dp[0] = dp[1] = 1，dp[0]表示没有人。<br>定义dist(i, j), (i≠j)，i,j&gt;0时表示第i,j座位之间的距离，i*j=0时为∞。<br>转移方程dp[ i ] = sum( dp [ j ] where dist(i, j)&gt;=6 and j &lt; i)。所求的方法总数即sum(dp)。<br>时间复杂度O(n)，空间复杂度O(n)。

<p>应该可以立个flag。做标记。</p>

<p>dp[i]是考虑前i个座位(注意是座位，不是尺)，符合要求的，且有人坐的安排数量<br>dp[i]  = dp[i-1] + dp[j] + 1<br>其中dp[i-1]是继承了前i-1个位置的数量，表示i这位置不坐人，dp[j]是i前面最近的一个距离大于6的位置下标，这个不一定有，表示i这位置坐人，最后加一表示前面都不坐人，只坐i位置的情况<br>初始状态dp[0]  = 1，答案是dp[n-1]  + 1，全没人的情况<br></p>

<p>这就类似力扣股票交易问题了。</p>

这个每个座位宽1尺很骚啊。让我回到了小学时代数学应用题。。。<br><br>我觉得dp算法题应该假设座位只是一个点。

<p>兄弟这道题你还想要代码吗？这个我有思路了。</p>

<div data-type="normal">这题已经写出来了，不过也想看看你怎么做。</div><div data-type="normal">老哥，能加个wei信（同虎扑id一样yashirq）吗？刚刚那个有点问题想问你，赶着交作业，万分火急</div>

<div>疫情期间，电影院恢复营业，但规定要保持社交距离。每两个观众之间要保持6尺距离，每个座位宽1尺。</div><br><div>假设 n>=0，电影院一排有 n+1 个座位。给出一个由非负整数组成的列表 A=[1,...,n], A 表示第 i 个座位和第 i+1个座位之间的距离。如何通过动态规划 (dynamic programming) 找出符合要求的座位安排的数量？</div><br><div>例子：</div><br><div>A=[2,3]，因此有3个座位，第一个座位和第二个座位的距离是2尺，第二个座位和第三个座位的距离是3尺。</div><br><div>如果没有观众，则只有1种摆法：口口口</div><br><div>如果有1个观众，则有3种摆法：X口口 或者 口X口 或者 口口X</div><br><div>如果有2个观众，则有一种摆法：X口X （因为座位宽1尺，2+1+3=6尺）</div><br><div>所以一共有5种摆法。</div><br><br><div>在知乎邀请了两天都没人回答，果然有问题还是要来找虎扑大佬</div><br><br><div>原题来了</div><br><div></div><br><div></div>

疫情期间，电影院恢复营业，但规定要保持社交距离。每两个观众之间要保持6尺距离，每

一道算法面试题，会动态规划的都来

yashirq

<div data-type="normal">疫情期间，电影院恢复营业，但规定要保持社交距离。每两个观众之间要保持6尺距离，每个座位宽1尺。</div><br data-tag="p"/><div data-type="normal">假设 n&gt;=0，电影院一排有 n+1 个座位。给出一个由非负整数组成的列表 A=[1,...,n], A[i] 表示第 i 个座位和第 i+1个座位之间的距离。如何通过动态规划 (dynamic programming) 找出符合要求的座位安排的数量？</div><br data-tag="p"/><div data-type="normal">例子：</div><br data-tag="p"/><div data-type="normal">A=[2,3]，因此有3个座位，第一个座位和第二个座位的距离是2尺，第二个座位和第三个座位的距离是3尺。</div><br data-tag="p"/><div data-type="normal">如果没有观众，则只有1种摆法：口口口</div><br data-tag="p"/><div data-type="normal">如果有1个观众，则有3种摆法：X口口 或者 口X口 或者 口口X</div><br data-tag="p"/><div data-type="normal">如果有2个观众，则有一种摆法：X口X （因为座位宽1尺，2+1+3=6尺）</div><br data-tag="p"/><div data-type="normal">所以一共有5种摆法。</div><br data-tag="p"/><br data-tag="p"/><div data-type="normal">在知乎邀请了两天都没人回答，果然有问题还是要来找虎扑大佬</div><br data-tag="p"/><br data-tag="p"/><div data-type="normal">原题来了</div><br data-tag="p"/><div data-type="normal"></div><br data-tag="p"/><div data-type="normal"></div><br data-tag="p"/>

虎扑体育网

这些回复亮了