[LeetCode]1621. Number of Sets of K Non-Overlapping Line Segments 动态规划js版

题目描述

LeetCode原题链接:1621. Number of Sets of K Non-Overlapping Line Segments

Given n points on a 1-D plane, where the ith point (from 0 to n-1) is at x = i, find the number of ways we can draw exactly k non-overlapping line segments such that each segment covers two or more points. The endpoints of each segment must have integral coordinates. The k line segments do not have to cover all n points, and they are allowed to share endpoints.

Return the number of ways we can draw k non-overlapping line segments. Since this number can be huge, return it modulo 10^9 + 7.

 

Example 1:

[LeetCode]1621. Number of Sets of K Non-Overlapping Line Segments 动态规划js版

Input: n = 4, k = 2
Output: 5
Explanation: The two line segments are shown in red and blue.
The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.

Example 2:

Input: n = 3, k = 1
Output: 3
Explanation: The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.

Example 3:

Input: n = 30, k = 7
Output: 796297179
Explanation: The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 10^9 + 7 gives us 796297179.

 

Constraints:

  • 2 <= n <= 1000
  • 1 <= k <= n-1

题目分析

这道题可以用动态规划来做,就是状态量会比较多一些,可能不大好理解。题目中给了n和k,那肯定我们先需要一个二维 dp[i][j] ,其中每个位置表示前0~i这些点分成j段有几种分法。这个比较直观,最终的结果就是dp[n-1][k]。现在我们来看对于遍历到的任意一个位置i,(i, 0)这个点和已经出现的线段能组成哪些新的情况,就用example1中的示意图作为例子, 假设当前遍历到了i=2这个位置:

case1: 将上一个位置(即:(1,0)点)的最后一根线段延长到当前位置,此时 (2,0) 成为了上一个位置最后一根线段延长后的新的终点,没有新的线段产生;

case2/case3: 将上一个位置(即:(1,0)点)最后一根线段的终点最为起点,将当前位置 (2,0) 作为终点,产生了一条新的线段(蓝色线段);

[LeetCode]1621. Number of Sets of K Non-Overlapping Line Segments 动态规划js版

注意这里为啥要把case2和case3分开呢?虽然它们都是以 (1,0) 为起点,(2,0) 为终点产生一条新线段,但由于 (1,0) 点之前的情况不同(空隙or某一线段终点),实际上最终结果是两种不同的情况。由此可见,我们还需要另外一种状态来标记某一点是否是最后一个线段的终点,即是否这个点之前挨着的是空隙。因此再在原有的二维dp数组上增加一个纬度,用来标识这种状态:

  • dp[i][j][0]: 前i个点分成j段并且i点不是最后一根线段终点时(最后一根线段没有延伸到i点)有几种分法
  • dp[i][j][1]: 前i个点分成j段并且i点是最后一根线段终点时(最后一根线段延伸到了i点)有几种分法

于是结合之前的分析,我们可以得到状态转移方程为:

  • dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1]  (如果不能延伸到 (i,0) 点,那么就要求在上一位置 (i-1,0) 点就要分割成j段)
  • dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j-1][1] + dp[i-1][j-1][0]  (如果能延伸到 (i,0)点,那么分别对应上图中的三种情况)

最后,初始化的时候 dp[0][0][0]=1,其余为0。最终结果返回 dp[n-1][k][0] + dp[n-1][k][1]

代码示例(JS)

 1 var numberOfSets = function(n, k) {
 2     let mod = 1000000007;
 3     let dp = new Array(n);
 4     for(let i = 0; i < n; i++) {
 5         dp[i] = new Array(k + 1);
 6         for(let j = 0; j <= k; j++) {
 7             dp[i][j] = new Array(2);
 8             dp[i][j].fill(0);
 9         }
10     }
11     dp[0][0][0] = 1;
12     for(let i = 1; i < n; i++) {
13         for(let j = 0; j <= k; j++) {
14             dp[i][j][0] = (dp[i-1][j][0] + dp[i-1][j][1]) % mod;
15             dp[i][j][1] = dp[i-1][j][1];
16             if(j > 0) {
17                 dp[i][j][1] = (dp[i][j][1] + dp[i-1][j-1][0] + dp[i-1][j-1][1]) % mod;
18             }
19         }
20     }
21     return (dp[n-1][k][0] + dp[n-1][k][1]) % mod;
22 };
上一篇:【Linux】下载


下一篇:5 银行存款到期日