Leetcode Java学习记录——动态规划基础_3

最大子序列和（最大子数组和）

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

思路

1. 暴力: n^2
2. DP:
   1. 分治（子问题）max_sum(i) = Max(max_sum(i-1), 0) + a[i]
   2. 状态数组定义 f[i]
   3. DP方程 f[i] = Max(f[i-1] , 0) + a[i]

题解

第一步按照上述步骤写出dp解法：

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];for(int i = 1; i<nums.length ; i++){if(dp[i-1] < 0){dp[i] = nums[i];}else{dp[i] = dp[i-1] + nums[i];}}// 返回dp数组中的最大值for(int dpElement : dp){if(dp[0]<dpElement){dp[0] = dpElement;}}return dp[0];}
}

可以优化，dp数组其实可以用nums本身替换，省去额外空间。

    public static int maxSubArrayDP2(int[] nums) {for(int i = 1; i<nums.length ; i++){if(nums[i-1] > 0){nums[i] = nums[i-1] + nums[i];}}// 返回dp数组中的最大值for(int dpElement : nums){if(nums[0]<dpElement){nums[0] = dpElement;}}return nums[0];}

或者直接用一个int

public int maxSubArray(int[] nums) {// int res = 0;// int sum = nums[0];// 初始值别搞错了int res = nums[0];int sum = 0;for(int num :nums){if(sum<0){sum = num;}else{sum += num;}res = Math.max(sum,res);}return res;}

零钱兑换 coin change

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

思路

类似爬楼梯问题

1. 暴力法 —— 递归-指数级
2. BFS —— 递归状态树，广度优先遍历
3. DP

题解

class Solution {public int coinChange(int[] coins, int amount) {//分治子问题//dp数组int max = amount+1;int[] dp = new int[max];Arrays.fill(dp,max);//因为要用min获取新值，就设置max为初始值dp[0]=0;//注意设置dp0//dp方程for(int i=1;i<=amount;i++){for(int j = 0; j<coins.length; j++){if(coins[j] <= i){//注意条件dp[i] = Math.min(dp[i] , dp[i-coins[j]] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}
}