最大子数组和 动态规划 public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) return 0; int[] dp = new int[nums.length]; dp[0] = nums[0]; int maxSum = dp[0]; for (int…

爬楼梯 爬第n阶楼梯的方法数量，等于 2 部分之和： 爬上 n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶 爬上 n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶 class Solution { public int climbStairs(int n) { // dp[i] 表示爬到第i层台阶的方法有多少种 int[] dp = new …

法1：动态规划 先贴个递归版本: int cutRope(int n) { // write code here if(n <= 4) return n; int res = 0; for(int i = 1; i < n; i++){ // 从i=1开始 表示第一刀剪下的长度 res = max(res, max(cutRope(n-…

字符串处理 没想到是动态规划题，感觉特别难 LCR 137. 模糊搜索验证 - 力扣（LeetCode） 法1：DP 用f[i][j]表示s的前i个字符与p的前j个字符是否能匹配。考虑情况： p的第j个字符是小写字符：f[i][j] = f[i-1][j-1] （if s[i] = p[j]）f[i][j] = false （if s[i] ≠ p…

动态规划 方法1，可以通过暴力On^2的方法，循环两次求出每个子数组的和对比。 法2.DP 设dp[i]，dp[i]代表以array[i]为结尾的连续子数组最大和。 转移方程为，dp[i] = max(array[i]，dp[i-1] + array[i])，理解如下： 因为以第n个数为结尾，所以array[n]是必然被选择的 基于dp[n-1]的…

NO7斐波那契数列 用递归的写法，复杂度将是O(2^n)级别的，无法忍受。 用三个变量存储递归的中间值，时间复杂度能到O(n)。    public int Fibonacci (int n) {        // write code here       int t1 = 1;       int t2 = 1;       int t3 =…