标签为 [动态规划] 的文章

打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。 示例 1: 输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2: 输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号 ......

买卖股票的最佳时机

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 暴力,时间复杂度O(n*n) 123456789101 ......

剑指offer——剪绳子

题目: 给你一根长度为n的绳子,请把绳子剪成m段 (m和n都是整数,n>1并且m>1)每段绳子的长度记为k[0],k[1],…,k[m].请问k[0]k[1]…*k[m]可能的最大乘积是多少? 例如,当绳子的长度为8时,我们把它剪成长度分别为2,3,3的三段,此时得到的最大乘积是18. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061public class 剪绳子 {     public static int jsz2(int length) {         if(length < 2)  ......

面试指南——字符串的交错组成

题目: 现在有3个字符串s1,s2,s3,我们需要判断s3是否是由s1和s2交错组成的。对于三个字符串A,B,C。我们称C由A和B交错组成当且仅当C包含且仅包含A,B中所有字符,且对应的顺序不改变 例如s1=”abc”,s=”1234d”,s3=”ab1234dc”,那么s3是由s1和s2交错组成的,如果s3=”ab1234cd”,则s3不是由s1和s2交错组成的。 /* * str1长度为M,str2长度为N, * aim由str1和str2组成,所以长度为M+N,如果长度不对的话返回false,生成m+1,n+1大小的Boolean类型dp矩阵, * dp[i][j]的值代表aim[0 ......

面试指南——最小编辑代价

题目描述: 给定两个字符串str1和str2,再给定三个整数ic,dc,rc,分别代表插入、删除、替换一个字符的代价,返回将str1编辑成str2的最小代价。 举例: str1=”abc” str2=”adc” ic=5 dc=3 rc=2,从”abc”编辑到”adc”把b替换成d代价最小,为2; str1=”abc” str2=”adc” ic=5 dc=3 rc=10,从”abc”编辑到”adc”,先删除b再插入d代价最小,为8; /* * 首先生成M+1,N+1的dp矩阵,dp[i][j]代表str1[0…i-1]编辑成s ......

面试指南——最长公共子序列问题

题目 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB 则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA /* * 以下dp[0…M-1]相当于dp[0]~dp[M-1] * str1.length = M;str2.length = N ==>生成M*N大小的dp矩阵, * dp[i][j]的含义:str1[0…i]和str2[0…j]的最长公共子序列的长度 * 从左到右,从上到下,计算dp矩阵 * 1.dp第一列即dp[0…M-1][0],dp[i][0]的含义是str1[0..i]和str2[0]的最长公共子序列的长度 * str ......

面试指南——最长公共子串问题

题目: 给定两个字符串,求出它们之间最长的相同子字符串的长度。 1234567891011121314/*  * 公共子串需要连续,公共子序列不需要连续  * dp矩阵第一列dp[0...M-1][0],如果str1[i]==str2[0],令dp[i][0]=1,否则dp[i][0]=0;  * dp矩阵第一行dp[0][0...N-1],如果str1[0]==str2[j],令dp[0][j]=1,否则dp[0][j]=0;  * 其他位置从左到右,从上到下计算,dp矩阵有以下两种情况:  * a.如果str1[i]!=str2[j],说明在必须把str1[i]和str2[j]当做公共子串的最后一个字符是不可能的,所以dp[i][j]=0;  * b.如 ......