概述 在做动态规划题时，常常陷入困惑，面对的几个挑战分别是 d数组如何设置？设置成一维还是二维？dp[n]还是dp[n+1]? 状态转移方程怎么考虑？ 分类 自我比较带约束 最长回文子串 设置dp[n][n],dp[i][j]表示s[i:j]的回文长度 最长的括号子串 设置dp[n],dp[i]表示s[:i]的子串长度 买卖股票的最好时机 设置dp[n],dp[i]表示s[:i]的利润 矩阵的最小路径和 设置dp[n][m],dp[i][j]表示到达矩阵[i][j]的路径和 求矩阵路径数 设置dp[n][m],dp[i][j]表示到达矩阵[i][j]的路径数 两两比较带约束 最小编辑代价 ...

题目描述 给出一个仅包含字符'('和')'的字符串，计算最长的格式正确的括号子串的长度。对于字符串"(()"来说，最长的格式正确的子串是"()"，长度为2.再举一个例子：对于字符串")()())",来说，最长的格式正确的子串是"()()"，长度为4. 示例1 输入"(()"返回值2 思路 Q1：dp如何设置？ 一开始我设置dp[n+1][n+1],因为这题感觉和回文子串有点想，然而最后发现并不行，看过题解后发现别人设置dp[n+1],dp[i]表示s[:i]的结果。 Q2：状态转移方程 看的别人题解，十分地巧妙，具体可看https://leetcode-cn.com/problems/lon...

题目描述 给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。 示例1 输入"1A2C3D4B56","B1D23CA45B6A"返回值"123456"说明"123456"和“12C4B6”都是最长公共子序列，任意输出一个。 思路 Q1：dp数组设置？ 两个字符串比较，设置dp[m+1][n+1],dp[i][j]表示字符串1[:i]和字符串2[:j]比较的结果 Q2:状态转移方程？ 一开始写成dp[i][j]=dp[i-1][j-1]+chs1[i-1]==chs2[j-1]?1:0;结果不对。 后来想到，如果不等的话，应该和dp[i][j...

题目描述 一个机器人在m×n大小的地图的左上角（起点）。机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？ 示例 输入2,1返回值1 思路 Q1:dp数组如何设置？二维数组中求一条路径，一般设置dp为二维数组。dp[i][j]表示到达ij位置的结果。code import java.util.*; public class Solution { public int uniquePaths (int m, int n) { if(m<=0 || n<=0)return 0; int[][] dp = new i...

题目描述 给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。 示例1 输入"abc","adc",5,3,2返回值2 思路 Q1：dp设置一维还是二维？涉及2个数组的比较，一般设置二维数据dp[i][j],元素ij表示一号数组[:i]和二号数组[:j]的比较结果。 Q2：状态转移方程怎么写？写到else时，关于三种修改方式的状态转移想不出来，看别人的，顿时感到巧妙。ic_sum = dp[i][j-1]+ic; dc_sum = dp[i-1][j]+dc; rc_sum = dp[i-1][j...

题目描述 给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。 示例1 输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]返回值12 思路 这题的转移方程很好写，dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+matrix[i][j]; 但是在做这题时，我第一次没过。原以为将dp设置为[n+1][m+1]能够自动初始化最左列和最上行的数，没想到并不能做到。 因此这题必须要首先初始化左列和上行。 code import...

题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。 示例1 输入"ab"返回值["ab","ba"] code import java.util.*; public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String&...

题目描述 假设你有一个数组，其中第\ i i 个元素是股票在第\ i i 天的价格。你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。 示例1 输入[1,4,2]返回值3 思路 这种有点像双指针的问题，使用以下dp模板：一维数组，i往右遍历，j从i开始向左遍历。 code1中状态转移方程为dp[i] = Math.max(dp[i-1],prices[i]-prices[j])。然而是错误的，测试后只过了一半左右。经过调试后发现，在j循环中，计算的前一个dp[i]会被覆盖，因此在code2中又加了一个max函数。当然code3中不用数组也就不...

题目描述 对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。给定字符串A以及它的长度n，请返回最长回文子串的长度。 示例1 输入"abc1234321ab",12返回值7 思路 1.转移方程容易想，但两个指针的移动方向容易出错。2.应该A指针向右走，B指针从A开始向左走，目的是B指针扫过的范围A已经走过，才能执行动态规划。 code import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { boolean [][]dp = ...

题目 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。提示：num1 和num2 的长度都小于 5100num1 和num2 都只包含数字 0-9num1 和num2 都不包含任何前导零你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式 code class Solution { public String addStrings(String num1, String num2) { int i = num1.length() - 1, j = num2.length() - 1, add = 0; ...

数组 Array dataType[] arrayRefVar = new dataType[arraySize]; //声明 dataType[] arrayRefVar = {value0, value1, ..., valuek}; //声明 int[] array2 = array1.clone(); //复制数组 arrayRefVar.length //长度 TestArrays.output(array); //打印数组 Arrays.fill(array, 5); //填充数组 Arrays.sort(array1, 2, 7); // 对数组的第2个到第6个进行排序进行升序排...

题目描述 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。窗口大于数组长度的时候，返回空 示例1 输入[2,3,4,2,6,...

和为S的两个数字-12行简洁写法 题目描述 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。输出描述:对应每个测试案例，输出两个数，小的先输出。 思路 使用双指针即可，但须知最先找到的解即为最优解 code class Solution { public: vector<int> FindNumbersWithSum(vector<int> array,int sum) { int l=0,r=array.size()-1; while(l<r...

两个链表的第一个公共结点 题目描述 输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的） 思路 1.做这题时，我有许多想法，但其中一种做法最为简单粗暴，堪称邪门做法，和其他人的做法都不一样，因此记录下来。 正道做法 比较直接的做法是，让两个链表的长度相等，然后使用双指针即可。至于如何让两个链表的长度相等，就是将b链表拼接到a链表后，同时让a链表拼接到b链表后。 class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, L...