哈哈哈哈鹅

题解

/ 注册

全部文章 / 题解（共7篇）

题解 | #求正数数组的最小不可组成和#动态规划 01背包问题

先找到数组中的最小值min，以及元素最大和add；按照0/1背包问题，我们可以列出如下表格： j表示组成和也就是背包的容量的组成情况，a[i]表示前i个物品任意选放的最大价值，i表示物品下标，dp[j]表示背包容量为...

Java 动态规划背包

2022-03-29

0 298

题解 | #编辑距离#

public class Subsequence { public static int numDistinct(String s, String t...

Java 动态规划

2021-11-19

0 487

题解 | #编辑距离#动态归划

可用二维数组i,j表示从word1的前i个字符到word2的前j个字符 dp[i][j]表示由word1的前i个字符转换为word2的前j个字符的最小编辑距离。状态公式：有两种情况： 1.当第i个字符和第j个字符相等时，那么从i到j的最小编辑距离只需要计算前i-1个字符到前j-1个字符的最小编...

Java 动态规划

2021-11-17

0 406

分割回文串-ii，优化算法之利用二维数组存储回文真值

//这是对前面回文串分割的优化算法，这个时间复杂度是O(n^2) // 方法是计算最小分割次数时，不用再去遍历字符串判断是否回文，而是先将字符串是否回文的结果保存下来，用一个二维数组来保存，i表示开始字符，j表示结束字符 //判断字符串是否回文就变成了求（i,j)区间是否是回文字符串，因此也可以用动...

Java 字符串动态规划

2021-11-15

0 387

题解 | #分割回文串-ii#动态规划算法

//时间复杂度O（n^3) public class PalindromeString { //判断回文串 public static boolean&n...

Java 动态规划

2021-11-15

0 341

题解 | #求路径# 简单易理解的动态规划算法

动态规划算法分析： 1.问题：求(0,0)到(m-1,n-1)的最小路径之和,更新数组grid(i,j)表示为到达这个位置的最短路径之和 2.状态定义：转化为子问题就是求(0,0)到(i,j)的最短路径之和，但是要首先计算第一行和第一列的这些位置的最短路径之和，注意处理越界的问题 3.状态转移...

Java 动态规划

2021-11-10

0 322

题解 | #求路径# 超详细动态规划算法分析

动态规划算法分析： 1.问题：求第一个点到最后一个点的路径数之和 2.状态定义：求(0,0)点到(i,j)点的路径数之和 3.状态转移方程：定义一个数组存储到每个点的路径数之和，因为只能向下或向右移动，所以点(i,j)的路经数之和numpath(i,j)=numpath(i-1,j)+numpa...

Java 动态规划

2021-11-10

0 410