不见武陵豪杰墓

分类

java(8) java设计模式(4) Leetcode(33) Spring系列(11) 剑指offer(14) 排序算法(1) 数据库(3) 数据结构(5) 未归档(1) 计算机网络(5) 设计模式(1) 闲思(1)

/ 注册

全部文章（共11篇）

最长公共子序列(LCS)

输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3 解析:定义dp[i][j]为s1的1--i序列和s2的1--j序列的最长公共子序列。如果s1的第i个...

动态规划

2020-05-25

0 487

编辑距离

输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 解析...

动态规划

2020-05-25

0 365

找零问题

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为的商品，请问最少他会收到多少硬币？解析1：数学方法。%为取余，/为取商 import java.util.Scanner; public class Main{ ...

动态规划

2019-12-28

0 582

01背包

解析：动态规划。1，dp[i][j]为背包容量为j时装前i个的最大价值。所求的是dp[5][9]。2，初始化数据，因为i=1时，只要j>w[i]就能装第一个，所以是v[i]。当j=0时，直接为0。3，递推关系式，当装的动第i个(j>w[i])时，dp[i][j] = max(dp[i-1...

动态规划

2019-12-28

0 412

打家劫舍

链状输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。解析:动态规划。1dp[i]为偷第i家时最大金额。2若是0，1...

动态规划

2019-12-26

0 465

不同路径

无障碍型一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？解析:动态规划。1定义数组,dp[i][j]为机器人到i，j点的方法数。...

动态规划

2019-12-26

0 463

最长回文子串

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。输入: "cbbd" 输出: "bb" 解析:动态规划三步骤。1定义数组，dp[i]j为i到j是否是回文子符串。2...

动态规划

2019-12-26

1 413

最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 输入: "()(())" 输出: 6 解释: 最长有效括号子串为 "()((...

动态规划

2019-12-25

0 536

从八皇后到全排列

八皇后问题代码说明:board.size()为8，row从0开始。根据递归，假设一个答案从第一行第二个元素开始，那么当他完成了这个函数，应该回溯时，将路上的Q变为“.”,这样回溯到第一行时，继续进行未竟之事业。全排列问题代码说明:1，2，3到1，3，2.只有当第一次的i到3时才会结束回溯。

动态规划

2019-12-12

0 351

动态规划之最小路径和

输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。解析1(二维数组法)：假设dp[i][j]是从ij点到最右下角元素的最小路径，那么dp[j][j]=min(dp[i+1][j],dp[i][j+1])+当...

动态规划

2019-12-10

0 523