当前位置: 首页 > article >正文

动态规划理论基础和习题【力扣】【算法学习day.25】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴!!!


习题

1.最后一块石头的重量II

题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode)

题面:

代码:

class Solution {
    public int lastStoneWeightII(int[] ss) {
        int n = ss.length;
        int sum = 0;
        for (int i : ss) sum += i;
        int t = sum / 2;
        int[][] f = new int[n + 1][t + 1];
        for (int i = 1; i <= n; i++) {
            int x = ss[i - 1];
            for (int j = 0; j <= t; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= x) f[i][j] = Math.max(f[i][j], f[i - 1][j - x] + x);
            }
        }
        return Math.abs(sum - f[n][t] - f[n][t]);
    }
}

2.目标和

题目链接:494. 目标和 - 力扣(LeetCode)

题面:

代码:

class Solution {
    private int[] nums;
    private int[][] memo;

    public int findTargetSumWays(int[] nums, int target) {
        int s = 0;
        for (int x : nums) {
            s += x;
        }
        s -= Math.abs(target);
        if (s < 0 || s % 2 == 1) {
            return 0;
        }
        int m = s / 2; // 背包容量

        this.nums = nums;
        int n = nums.length;
        memo = new int[n][m + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1); // -1 表示没有计算过
        }
        return dfs(n - 1, m);
    }

    private int dfs(int i, int c) {
        if (i < 0) {
            return c == 0 ? 1 : 0;
        }
        if (memo[i][c] != -1) { // 之前计算过
            return memo[i][c];
        }
        if (c < nums[i]) {
            return memo[i][c] = dfs(i - 1, c); // 只能不选
        }
        return memo[i][c] = dfs(i - 1, c) + dfs(i - 1, c - nums[i]); // 不选 + 选
    }
}

后言

上面是动态规划的基本概念和部分习题,下一篇会有其他习题,希望有所帮助,一同进步,共勉!  


http://www.kler.cn/a/383671.html

相关文章:

  • 基于Spring Boot的九州美食城商户一体化系统
  • 【RAG实战】Prompting vs. RAG vs. Finetuning: 如何选择LLM应用选择最佳方案
  • UG NX二次开发(C#)-机电概念设计-UIStyler中selection块选择信号等对象的过滤器设置
  • 单片机:实现自动关机电路(附带源码)
  • Android使用PorterDuffXfermode模式PorterDuff.Mode.SRC_OUT橡皮擦实现“刮刮乐”效果,Kotlin(2)
  • XMLHttpRequest的基础知识
  • apache poi 实现下拉框联动校验
  • MySQL表转移数据的三种方式
  • 【Python进阶】Python中的网络爬虫策略:高效数据抓取与解析
  • 数据库优化指南:如何将基本功能运用到极致?
  • Qt(程序打包)
  • ubuntu 异常 断电 日志 查看
  • 半导体设备行业,多单收购
  • 微信小程序大学生闲置物品交易平台+ssm(lw+演示+源码+运行)
  • 势不可挡 创新引领 | 生信科技SOLIDWORKS 2025新品发布会·苏州站精彩回顾
  • vue实现websocket实时短消息通知
  • 完全背包模板总结
  • 设计者模式之策略模式
  • 《构建一个具备从后端数据库获取数据并再前端显示的内容页面:前后端实现解析》
  • 集中管理用户名和密码,定期修改密码快捷方便
  • 参数跟丢了之JS生成器和包装器
  • PostgreSQL核心揭秘(三)-元组结构
  • 【科普】conda、virtualenv, venv分别是什么?它们之间有什么区别?
  • 讲讲RabbitMQ 性能优化
  • Qt中弹出窗口的实现与鼠标事件处理
  • ctfshow(91,96,97)--PHP特性