LEETCODE 1359. Count All Valid Pickup and Delivery Options 解题思路分析

题目大意:

有效的快递序列数目

给你 n 笔订单,每笔订单都需要快递服务。

请你统计所有有效的 收件/配送 序列的数目,确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。

由于答案可能很大,请返回答案对 10^9 + 7 取余的结果。

示例 1:

输入:n = 1
输出:1
解释:只有一种序列 (P1, D1),物品 1 的配送服务(D1)在物品 1 的收件服务(P1)后。

示例 2:

输入:n = 2
输出:6
解释:所有可能的序列包括:
(P1,P2,D1,D2),(P1,P2,D2,D1),(P1,D1,P2,D2),(P2,P1,D1,D2),(P2,P1,D2,D1) 和 (P2,D2,P1,D1)。
(P1,D2,P2,D1) 是一个无效的序列,因为物品 2 的收件服务(P2)不应在物品 2 的配送服务(D2)之后。

示例 3:

输入:n = 3
输出:90

提示:

  • 1 <= n <= 500

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1359

解题思路分析:

这是一道典型的动态规划问题。用数学语言来描述的话,题目实际上在求所有接单和发单的排列组合。解题时,我们需要定义当前没有接的单子数量n,以及手中还未发送的单子数量p。初始时,n等于题目给出的单子数量,p等于0。对于任意一个时间点,如果n大于0,说明我们可以接一单,n个单子中的任意一单都是我们可以接收的对象,接收后n的数量减一,同时手中单子数量p加一,因此当前时间点接收一单的可能性为:

res = n * help(p+1, n-1);

另外,在当前时间点,如果手中的单子数量p大于0,我们也可以选择发单,发单时可以在p个单子中任选一个发送,发送后,p的数量减一,而n不变,因此当前时间点发送一单的可能性为:

res = p * help(p-1, n);

将上面两个结果相加即是当前时间点所有操作的排列组合数。

另外递归时,我们需要使用记忆数组来作为辅助,避免重复情况的计算。

如果你对动态规划解法或者是记忆数组还不太了解,可以参照我之前分享过的文章:

LEETCODE常见算法之动态规划DP超详细白话讲解(上)

LEETCODE常见算法之动态规划DP超详细白话讲解(下)

实现代码:

int[][] memo; // 记忆数组
public int countOrders(int n) {
    // 初始化记忆数组
    memo=new int[n+1][n+1];
    // 递归求解
    return help(0,n);
}
// p为手中的单子数
// n为还未接收的单子数
// 返回值为,手中有p个单子,并且还有n个单子未接收的情况下的排列组合数 
int help(int p, int n){
    // 如果p和n都是0,默认返回1
    if(n==0&&p==0) return 1;
    // 如果记忆数组中存在当前解,直接返回
    if(memo[p][n]>0)return memo[p][n];
    // 返回结果
    int res=0;
    // 如果还有未接的单子,我们可以选择接一单
    if(n>0){
        // 从n个未接的单子中任意接一单后的组合数
        res+=((long)n*help(p+1,n-1)%1000000007);
    }
    // 如果还有未发送的单子,我们可以选择发送一单
    if(p>0){
        // 从n个未发送的单子中任意发送一单后的组合数
        res+=((long)p*help(p-1,n)%1000000007);
    }
    // 将当前结果保存至记忆数组
    memo[p][n]=res;
    // 返回当前结果
    return res;
}

本题解法执行时间为30ms。

Runtime: 30 ms, faster than 8.67% of Java online submissions for Count All Valid Pickup and Delivery Options.

Memory Usage: 41 MB, less than 100.00% of Java online submissions for Count All Valid Pickup and Delivery Options.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1359-count-all-valid-pickup-and-delivery-options-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。