详解线性 DP 解法,以及两个「可优化」的点 |Java 刷题打卡

简介: 详解线性 DP 解法,以及两个「可优化」的点 |Java 刷题打卡

题目描述



这是 LeetCode 上的 1269. 停在原地的方案数 ,难度为 困难


Tag : 「线性 DP」


有一个长度为 arrLen 的数组,开始有一个指针在索引 0 处。


每一步操作中,你可以将指针向左或向右移动 1 步,或者停在原地(指针不能被移动到数组范围外)。


给你两个整数 steps 和 arrLen ,请你计算并返回:在恰好执行 steps 次操作以后,指针仍然指向索引 0 处的方案数。


由于答案可能会很大,请返回方案数 模 10910^9109 + 7 后的结果。


示例 1:


输入:steps = 3, arrLen = 2
输出:4
解释:3 步后,总共有 4 种不同的方法可以停在索引 0 处。
向右,向左,不动
不动,向右,向左
向右,不动,向左
不动,不动,不动
复制代码


示例  2:


输入:steps = 2, arrLen = 4
输出:2
解释:2 步后,总共有 2 种不同的方法可以停在索引 0 处。
向右,向左
不动,不动
复制代码


示例 3:


输入:steps = 4, arrLen = 2
输出:8
复制代码


提示:


  • 1 <= steps <= 500
  • 1 <= arrLen <= 10610^6106


动态规划



这道题的可变维度分析不算复杂,因此这次就不从 DFS 开始给大家分析了。


定义 f[i][j]f[i][j]f[i][j] 代表当前剩余操作数为 iii,所在位置为 jjj 的所有方案数。


起始位置为 000,操作次数为 stepstepstep,即有初始化条件 f[step][0]=1f[step][0] = 1f[step][0]=1f[0][0]f[0][0]f[0][0] 则是我们的最终答案。


不失一般性的考虑 f[i][j]f[i][j]f[i][j] 可以由哪些状态转移而来:


  • 由「原地」操作到达当前状态,消耗一次操作,此时由状态 f[i+1][j]f[i + 1][j]f[i+1][j] 转移而来
  • 由「向左」操作到达当前状态,消耗一次操作,此时由状态 f[i+1][j+1]f[i + 1][j + 1]f[i+1][j+1] 转移而来
  • 由「向右」操作到达当前状态,消耗一次操作,此时由状态 f[i+1][j−1]f[i + 1][j - 1]f[i+1][j1] 转移而来


求的是方案数,即最终的 f[i][j]f[i][j]f[i][j] 为三者累加值。


同时我们发现 f[i][x]f[i][x]f[i][x] 依赖于 f[i+1][y]f[i + 1][y]f[i+1][y],因此我们需要按照「stepstepstep 从大到小」的顺序进行转移。


同时我们根据「最终回到下标 000 位置」可以推断出,最远到达的位置为 step/2step / 2step/2(再远就回不来了)。将最远到达位置与数组最大下标取 minminmin 即可确定维度 stepstepstep 的范围。


代码:


class Solution {
    int mod = (int)1e9+7;
    public int numWays(int steps, int len) {
        int max = Math.min(steps / 2, len - 1);
        int[][] f = new int[steps + 1][max + 1]; 
        f[steps][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            for (int j = 0; j <= max; j++) {
                f[i][j] = (f[i][j] + f[i + 1][j]) % mod;
                if (j - 1 >= 0) f[i][j] = (f[i][j] + f[i + 1][j - 1]) % mod;
                if (j + 1 <= max) f[i][j] = (f[i][j] + f[i + 1][j + 1]) % mod;
            }
        }
        return f[0][0];
    }
}
复制代码


  • 时间复杂度:共有数量级为 step∗maxstep * maxstepmax 个的状态需要被转移。复杂度为 O(step∗max)O(step * max)O(stepmax)
  • 空间复杂度:O(step∗max)O(step * max)O(stepmax)


优化



1. 对时间复杂度进行「常数级别的优化」


f[0][0]f[0][0]f[0][0] 并不依赖于操作次数同为 000 的其他位置的状态,而只依赖于操作次数为 111 的特定位置的状态。同理其他状态也是。


因此我们会发现随着「可操作次数」的减少,「可达到的最远位置」下标也会逐步缩小。从目标状态 f[0][0]f[0][0]f[0][0] 进行倒推的话,会发现「可达到的最远位置」等于「可操作次数」。


所以其实可以从两者取一个 minminmin 就能够有效减少「无效状态」的计算。数据量越大,这个性质带来的剪枝效果越好。


PS. 为了方便你看到优化前后的差别,我增加了打印注释,使用测试数据 (500, 100000) 并打开注释,可以看到少计算了多少「无效状态」。


网络异常,图片无法展示
|


代码:


class Solution {
    int mod = (int)1e9+7;
    public int numWays(int steps, int len) {
        int max = Math.min(steps / 2, len - 1);
        int[][] f = new int[steps + 1][max + 1]; 
        f[steps][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            int edge = Math.min(i, max);
            // if (edge != max) System.out.println(edge + " " + max);
            for (int j = 0; j <= edge; j++) {
                f[i][j] = (f[i][j] + f[i + 1][j]) % mod;
                if (j - 1 >= 0) f[i][j] = (f[i][j] + f[i + 1][j - 1]) % mod;
                if (j + 1 <= max) f[i][j] = (f[i][j] + f[i + 1][j + 1]) % mod;
            }
        }
        return f[0][0];
    }
}
复制代码


  • 时间复杂度:共有数量级为 step∗maxstep * maxstepmax 个的状态需要被转移。复杂度为 O(step∗max)O(step * max)O(stepmax)
  • 空间复杂度:O(step∗max)O(step * max)O(stepmax)


2. 对空间复杂度进行「维度级别的优化」


这个优化思维难度就要低很多了,利用 f[i][x]f[i][x]f[i][x] 依赖于 f[i+1][y]f[i + 1][y]f[i+1][y],使用「滚动数组」方式进行优化即可。


网络异常,图片无法展示
|


代码:


class Solution {
    int mod = (int)1e9+7;
    public int numWays(int steps, int len) {
        int max = Math.min(steps / 2, len - 1);
        int[][] f = new int[2][max + 1]; 
        f[steps&1][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            int edge = Math.min(i, max);
            int a = i & 1, b = (i + 1) & 1;
            for (int j = 0; j <= edge; j++) {
                f[a][j] = 0;
                f[a][j] = (f[a][j] + f[b][j]) % mod;
                if (j - 1 >= 0) f[a][j] = (f[a][j] + f[b][j - 1]) % mod;
                if (j + 1 <= max) f[a][j] = (f[a][j] + f[b][j + 1]) % mod;
            }
        }
        return f[0][0];
    }
}
复制代码


  • 时间复杂度:共有数量级为 step∗maxstep * maxstepmax 个的状态需要被转移。复杂度为 O(step∗max)O(step * max)O(stepmax)
  • 空间复杂度:O(max)O(max)O(max)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.1269 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
15天前
|
Java Spring
如何优化Java异步任务的性能?
本文介绍了Java中四种异步任务实现方式:基础Thread、线程池、CompletableFuture及虚拟线程。涵盖多场景代码示例,展示从简单异步到复杂流程编排的演进,适用于不同版本与业务需求,助你掌握高效并发编程实践。(239字)
125 6
|
21天前
|
数据采集 存储 弹性计算
高并发Java爬虫的瓶颈分析与动态线程优化方案
高并发Java爬虫的瓶颈分析与动态线程优化方案
|
2月前
|
安全 Java 编译器
new出来的对象,不一定在堆上?聊聊Java虚拟机的优化技术:逃逸分析
逃逸分析是一种静态程序分析技术,用于判断对象的可见性与生命周期。它帮助即时编译器优化内存使用、降低同步开销。根据对象是否逃逸出方法或线程,分析结果分为未逃逸、方法逃逸和线程逃逸三种。基于分析结果,编译器可进行同步锁消除、标量替换和栈上分配等优化,从而提升程序性能。尽管逃逸分析计算复杂度较高,但其在热点代码中的应用为Java虚拟机带来了显著的优化效果。
63 4
|
2月前
|
存储 人工智能 算法
Java 大视界 -- Java 大数据在智能医疗影像数据压缩与传输优化中的技术应用(227)
本文探讨 Java 大数据在智能医疗影像压缩与传输中的关键技术应用,分析其如何解决医疗影像数据存储、传输与压缩三大难题,并结合实际案例展示技术落地效果。
|
2月前
|
机器学习/深度学习 算法 Java
Java 大视界 -- Java 大数据机器学习模型在生物信息学基因功能预测中的优化与应用(223)
本文探讨了Java大数据与机器学习模型在生物信息学中基因功能预测的优化与应用。通过高效的数据处理能力和智能算法,提升基因功能预测的准确性与效率,助力医学与农业发展。
|
2月前
|
数据采集 搜索推荐 Java
Java 大视界 -- Java 大数据在智能教育虚拟学习环境构建与用户体验优化中的应用(221)
本文探讨 Java 大数据在智能教育虚拟学习环境中的应用,涵盖多源数据采集、个性化推荐、实时互动优化等核心技术,结合实际案例分析其在提升学习体验与教学质量中的成效,并展望未来发展方向与技术挑战。
|
2月前
|
机器学习/深度学习 算法 Java
Java 大视界 -- Java 大数据在智能物流运输车辆智能调度与路径优化中的技术实现(218)
本文深入探讨了Java大数据技术在智能物流运输中车辆调度与路径优化的应用。通过遗传算法实现车辆资源的智能调度,结合实时路况数据和强化学习算法进行动态路径优化,有效提升了物流效率与客户满意度。以京东物流和顺丰速运的实际案例为支撑,展示了Java大数据在解决行业痛点问题中的强大能力,为物流行业的智能化转型提供了切实可行的技术方案。
Java 数据库 Spring
59 0
|
1月前
|
算法 Java
Java多线程编程:实现线程间数据共享机制
以上就是Java中几种主要处理多线程序列化资源以及协调各自独立运行但需相互配合以完成任务threads 的技术手段与策略。正确应用上述技术将大大增强你程序稳定性与效率同时也降低bug出现率因此深刻理解每项技术背后理论至关重要.
92 16
|
2月前
|
缓存 并行计算 安全
关于Java多线程详解
本文深入讲解Java多线程编程,涵盖基础概念、线程创建与管理、同步机制、并发工具类、线程池、线程安全集合、实战案例及常见问题解决方案,助你掌握高性能并发编程技巧,应对多线程开发中的挑战。

热门文章

最新文章