//本题用动态规划求解，第一次完完全全按照自己思路实现，记录一下 // dp【n】设为以字符串第n个元素结尾的最长的子字符串 // 本题用hashMap<Character,Integer> 记录暂存的子字符串 // dp[n]的求解思路 循环遍历字符串 // 细分为 三种情况： //一.当 第i个字符等于 第i-1 个字符时 --前面的字符串已经不能达到题目所给的要求，所以直接清除，长度置为1 //二、 当 第i个字符 不 等于 第i-1 个字符时，且map中不含该字符时，说明该字符在当前子字符串中无重复，直接加一 //方程：dp【i】 = dp【i-1】 + 1 //三、 当 ...

//本题用动态规划求解，暴力搜索最简单 //设记忆化数组 为 dp【i】【j】i为天数 j长度为2 【0】【1】 dp代表了i天所持钱数 //0 代表今天不持股 1代表今天持股 //当今天不持股时 ，有两种情况 ： 昨天不持股，或者昨天卖出 //状态转移方程为：dp[i][0] = Math.max[dp[i-1][0],dp[i-1][1] + prices[i] //当今天持股时。有两种情况：昨天持股，或者昨天不持股，今天买入 //状态转移方程为：dp[i][1] = Math.max(dp[i-1][1], - prices[i]); import java.util.*; public...

//本题用动态规划求解 //数学归纳法找规律 发现为斐波那契数列 f（n） = f（n-1） + f（n- 2）！（关键） //以此建立状态转移方程求解 import java.util.*; public class Solution { public int rectCover(int target) { if (target <= 2){ return target; } int dp1 = 1; int dp2 = 2; int ans = 0; for (int i = 3; i <= target; i++) { ans = dp1 + dp2; dp1 = dp2; ...

//本题用动态规划求解 //果然数学还是卡人，这个题本身没难度，唯一难点就是在状态转移方程 //dp[n]设为到n的跳数 //f(n) = f(n-1) + f(n-2) +....+f(0) //f(n-1) = f(n-2) + f(n-3) +......+f(0) //所以 f（n） = 2 * f(n-1); dp[i] = 2 *dp[i-1] import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param number int整型 * @retu...

//个人感觉是动规最符合模板流程的题 //定义记录的数组 dp【n】 为f（n）的值 //初始化dp值 题给的 n=1/2时f（n） 等于1 dp[1]/dp[2] = 1 //构建状态转移方程 ：题给 f（n） = f（n-2） + f（n-1） //即为 dp[n] = dp[n-1] + dp[n-2] import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ public int Fibona...

import java.util.*; //动态规划 //设置dp【n】为到达n阶的跳法数，状态转移方程为dp【n】 = dp【n-1】 + dp【n-2】 //因为n- 2阶和n-1都可以一步跳到n public class Solution { public int jumpFloor (int number) { if (number ==1){ return 1; }else if (number == 2){ return 2; } int[] dp = new int[number + 1 ]; dp[0] = 0; dp[1] = 1; dp[2] = 2; for (int i...

//本题用动态规划解决 /*和求最长子序列和一样，可以看一下我上一篇文章，仅仅对子序列的长度做了记录 设置 right ，left ，maxRight ，maxLeft 分别记录实时左右长度和最长的长度 */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型一维数组 * @return int整型一维数组 */ public int[] FindGreatestSumOfSubArray (int[] array) { //当array长度为1时直接返回 if(...

//本题用动态规划求解 //本题第一种第二种方法思路大致相似，具体实现不同 //dp【i】和temp一个含义，是以第i个元素结尾的最大子数组的和 //转移方程为 ：dp[i - 1] > 0 ? dp[i] = dp[i-1] + array[i] : dp[i] = array[i]; //(表达式格式不对，但是意思就是这个意思，勿喷） public class Solution { public int FindGreatestSumOfSubArray (int[] array) { //参考大佬更简洁代码 //temp记录中间计算值 int temp = 0; //ans记录最大...

/*本人动规初学者，勿喷 本题解题思路：动规个人理解为寻找最优子结构，即构建状态转移方程，记录重复计算值，减少非必要计算次数 本题计算乘积为正数的子数组长度，设置两个数组，分别用于记录0-n中的最长的正负子数组长度，仅仅只判断符号 当传入两个数组的输入数组值inits[i]时，判断其正负，正数则正数数组直接加一，负数视情况看是否要置零 inits[i]为负时同理，设置一个值ans来存储最大值 当inits[i]输入为0时，正负数组都要置零，因为java数组默认初始化为0，所以直接空过这一次循环 0不是正整数 */ import java.io.*; public class Main { pu...