0. 动态规划分析
0.1 动态规划、递归和贪心算法的区别
动态规划就是利用分治思想和解决冗余的办法来处理问题，所以必然会有dp数组来实现记忆搜索，从而解决冗余，而分治思想就是递归的思想，总的问题可以分为若干相同的子问题，所有子问题的解合并即是该问题的解。
递归解决问题是一个自顶向下的思路，一直从最大的问题（顶）递归至小问题（下，底），只有小问题解决了，一层一层地返回，便可以得到最终的结果。
动态规划解决问题是一个自底而上的思路，从小问题（下）开始，把小问题的计算结果保存至dp数组中，计算更大的问题时会用到小问题的结果，直接调用而不必重新计算，直到最大问题。
贪心算法就是动态规划问题中的局部最优问题解，不要遍历当前子问题中的所有情况，一般只取当前最优的情况。
0.2 dp公式
dp[i][j]公式是为了求出当前的状态，需要再次搜索得到次解的索引，所以有索引变化，就有解的搜索。
所以，动态规划问题就是需要分析出，当前状态与前一个状态的对应，即当前问题的子问题的组合
0.3 动态规划问题的复杂度
由于动态规划一般用两个for循环实现，所以
时间复杂度是O(n^2)或O(mn)
空间复杂度是O(n^2)或O(n)
所以，一般都不是最好的算法，只是用来处理可以避免遗漏问题解
想要提高算法效率，继续抓住问题的特点可以找到更多隐藏的信息，提供解题的切入点，得到的效果就会不一样。
0.4 动态规划问题与深度优先或广度优先问题
动态规划问题和BFS与DFS问题在分析子问题时，有时候会遇到相同的子问题是类似的情况，总问题是多个子问题的综合，这是共同点
- 动态规划是全面处理最优问题，时间和空间复杂度比较大，但是可以优化，这是一个覆盖全部子问题的解决方法，重点是全面和最优
- 深度/广度优先遍历是如何更加高效地处理这个问题，讲到的是时间效率，降低时间复杂度，空间复杂度一般都是指数递增的，重点在优先
动态规划是有最优问题的，中间的子问题也有最优解，但是BFS与DFS是求解一个客观存在的唯一问题。比如，求二叉树的最长深度，这个是一个DFS问题，虽然有“最”字，但是这个客观存储的，不是最优问题。比如，求解二叉树的最浅分支，这是一个BFS问题，也是客观存在的，不是子问题有选择的问题。
0.5 辅助数组的作用
一般情况下，我们都会利用与原问题矩阵行列大于1的新数组来存储需要重复计算的数据，即原问题矩阵或数组分别为arr[n][m]和arr[n]，而辅助数组为dp[n+1][m+1]和dp[n+1]，目的是计算arr矩阵中的每一个位置的对应最优解，这就是动态规划问题的最优子问题的数据存储地方。
在此求解过程中，如果我们保持的数据只与前面几个数据有关，例如跳一步和跳两步这个问题，下一个问题只与之前的两个数据有关，所以交替保存数据，只用O(1)空间复杂度便可以实现动态规划问题。
1. （LeetCode） 单个币种无限个数的硬币找零
给你不同面值的硬币数组coins和总金额amount。 编写一个函数来计算您需要对amount金额的进行找零的最少数量的硬币。 如果这些金额不能由硬币的任何组合来找零，则返回'-1'。
例 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
例 2:
coins = [2], amount = 3
return -1.
注意:假设每一个币种的数量是无限的
题目分析
理论分析
理论分析是重复取所有coins，判断当前数额n可以找零取钱最少
dp(n) = min{ dp(n - coins[i]) + 1} , i = 0, 1, 2,..., m.
编程实现分析
每一次取值与已经存在的最小F(n)比较，选择最小的，因为我们只要知道最小的，中间的数据不必保存
dp(n) = min{ dp(n), dp(n - conins[i]) + 1}, i = 0, 1, 2,..., m.
问题剖析
由于本问题是一个单个币种可以重复选择的问题，所以这就意味着每取一个元素，后面可以取的情况与前一次是独立的，没有关系，独立重复处理。而对于给定字符串的组合问题，则是取了元素之后，能取的元素就少了一个。字符串组合和给定全部一个的币种的问题是一样的。
当前问题与上一次遇到的情况是一样的，如果把每一次取元素当作当前问题，下一次取值就是子问题，这种分析问题的方式比较容易理解
代码实现
public int coinChange(int[] coins, int amount){
if(coins.length < 1 || amount < 1) return -1;
int[] dp = new int[amount + 1];
for(int i = 1; i <= amount; ++i){
dp[i] = amount;
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];
}
2.币种无限个数的硬币找零组合
给你不同面值的硬币数组coins和总金额amount。 编写一个函数来计算组成该amount的组合的数量。每种硬币的个数是无限的。
注意：假设
- 0 <= amount <= 5000
- 1 <= coin <= 5000
- the number of coins is less than 500
- the answer is guaranteed to fit into signed 32-bit integer
例 1:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
有四种组合方式：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
例2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
例 3:
Input: amount = 10, coins = [10]
Output: 1
代码分析
求种类数，多少种方法，多少条路径等这类问题
只要开头走到结尾就算1种（1次），所以共有多少种方法，就是看分叉的次数，分叉次数就是总和。
代码实现
public class Solution {
public int change(int amount, int[] coins) {
int[] dp=new int[amount+1];
dp[0]=1;
for(int i=0;i<coins.length;i++){
for(int j=0;j<amount+1;j++){
if(j-coins[i]>=0){
dp[j]+=dp[j-coins[i]];
}
}
}
return dp[amount];
}
}
3.回文子串问题
3.1 Palindromic Substrings
题目描述
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同起始索引或结束索引的子字符串即使由相同的字符组成，也会被计为不同的子字符串。
例1：
输入： “abc”
输出： 3
说明：三个回文串：“a”，“b”，“c”。
例2：
输入： “aaa”
输出： 6
说明：六个回文串：“a”，“a”，“a”，“aa”，“aa”，“aaa”。
代码实现
public int countSubstrings(String s) {
int n = s.length();
int res = 0;
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
if(dp[i][j]) ++res;
}
}
return res;
}
复杂度更好的算法[1]
3.2 Longest Palindromic Substring
问题描述
给定一个字符串s，找到s中的最长回文子串。假设s的最大长度是1000。
例1：
输入： “babad”
输出： “bab”
注意： “aba”也是一个有效的答案。
例2：
输入： “cbbd”
输出： “bb”
思路分析
dp[i][j] 的定义如下面的公式：
则递归公式：
编程实现过程
输入:BCDFDECB
输出：DFD
代码实现
public String longestPalindrome(String s) {
int n = s.length();
String res = null;
boolean[][] dp = new boolean[n][n];
//依次从最后面进行迭代，前一轮迭代为可能的回文的第一个字符，然后依次进行比对是否与第一个字符相等，如果不等则直接为False，然后进行后续比对，如果找到相同的字符，则比对左斜下的子字符的回文信息，由于i+1，j-1，所以开始比对的是第i-1和第j-1字符是否相等，依次向里面靠拢，直到相遇。
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) { //dp[i+1][j-1]是一个左斜下的小回文
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);// j-i<3是在只有三个字符或四个字符为回文时的快速判断，不需要获取左斜下对角的值
if (dp[i][j] && (res == null || j - i + 1 > res.length())) { //找出比之前更长的回文，则更新字符串
res = s.substring(i, j + 1);
}
}
}
return res;
}
复杂度
Time complexity : O(n^2)
Space complexity : O(n^2)
复杂度更好的算法[2]
4.背包问题
4.1 背包问题的特点
给定了一个固定的容量结果数，计算最优解并且限制条件是这个固定容量
Max f(x)
s.t. w <= W
4.2 问题描述
有N件物品，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数），现在从中取出若干件物品放入容量为W的背包里。求背包能够装下的最大价值。
4.3 题目分析
实现固定体积装下最大价值的方法：
1.从物品索引开始，依次选择取本物品或不取物品。
2.对待第一个是这样，对待第二物品也是选择或不选择
3.选择或不选择，还有一个判断条件，就是选择的本物品的体积不能大于当前背包的剩余的空间
所以，本质上也是一个组合问题！从n个物品中选择m（m的取值从0至n）个，使m个物品的价值之和最大，这个最大就是最优问题。
4.4 上述分析的编程结果分析
依次分析结果，W1,W1W2,W2,W1W2W3,W2W3,...,Wn。
但是在中间由于增加了一个最优解，所以利用O(1)的空间复杂度就可以保存之前遍历的组合的最大价值。
4.5 代码实现
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int v = in.nextInt();
int[] dp = new int[v + 1];
int[] price = new int[n + 1];
int[] weight = new int[n + 1];
long max = 0;
for (int i = 1; i < n + 1; i++) {
weight[i] = in.nextInt();
price[i] = in.nextInt();
}
for (int i = 1; i < n + 1; i++)
for (int j = v; j > 0; j--)
if (j - weight[i] >= 0)
dp[j] = Math.max(dp[j], dp[j - weight[i]] + price[i]);
else
dp[j] = dp[j];
for (int i = 0; i < v + 1; i++)
max = max > dp[i] ? max : dp[i];
System.out.println(max);
}
}
5. Integer Break
本问题与背包问题也是一样的，分裂固定的总数，使相乘结果最优。
题目描述
给定一个正整数n，将其分解为至少两个正整数的和，并使这些整数的乘积最大化。返回您可以获得的最大产品。
例如，给定n = 2，返回1（2 = 1 + 1）; 给定n = 10，返回36（10 = 3 + 3 + 4）。
注意：你可以假设n不小于2且不大于58。
题目分析
数学的分析[1]:大于4的自然数，每次乘以3便可以，小于4的数枚举便可。
例如：
dp[8] = dp[3] * dp[3] * dp[2]
dp[11] = dp[3] * dp[8]
dp[4] = dp[2] * dp[2]
所以取值问题是尽量让被分的数离3接近，如果dp[2] * dp[2] > dp[3] * dp[1]
代码实现
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for(int i = 2; i <= n; i ++) {
for(int j = 1; j < i; j ++) {
dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
}
}
return dp[n];
}
5.Perfect Squares
问题描述
给定一个正整数n，找到与1, 4, 9, 16, ...相加的和为n的最小完美平方数。
例如，给定n = 12，返回3,因为12 = 4 + 4 + 4; 给n = 13，返回2,因为13 = 4 + 9。
问题分析
这实际上是一个背包问题的改进，每次减去的是一个数的平方（j^2），然后计算最小的减法操作次数
背包问题与零钱找零问题也是类似的，所以统称为“背包问题”
代码实现
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i <= n; ++i) {
int min = Integer.MAX_VALUE;
int j = 1;
while(i - j*j >= 0) {
min = Math.min(min, dp[i - j*j] + 1);
++j;
}
dp[i] = min;
}
return dp[n];
}
6. 字符串的距离和编辑问题
问题描述
对于序列S和T，它们之间距离定义为：
对二者其一进行几次以下的操作
(1)删去一个字符；
(2)插入一个字符；
(3)改变一个字符。
每进行上面任意一次操作，计数增加1。
将S和T变为同一个字符串的最小计数即为它们的距离（最优问题）
问题的递归思路分析
说明：dp[i][j] 表示截取字符S和T在第i和第j个字符之前的字符进行比对，这个相对于拿整个字符来处理，是子问题。
1.从两个字符串尾字符开始建立索引并向前走，如果两个字符相等则dp[i][j] = dp[i-1][j-1]
2.如果两个字符不等，则从三种选择中选择一种操作进行本次更改（以下b和c中有多个重复的情况）：
(a)修改S或T的这个字符，让其等于另外一个字符，相等后就表示两个字符相等了，也就是第一种情况，但操作了一回，所以为dp[i][j] = dp[i-1][j-1] + 1
(b)删除S或T的这个字符，然后进行下一次比较，此时这两个字符还是不等于，也就回到了下一次比较的情况，同时比较删除S中这个不等的字符得到的结果与删除T中的这个字符得到的结果，取小的，如dp[i][j] = min{ dp[i-1][j] + 1, dp[i][j-1] + 1 }
(c)在S或T中插入一个字符让这两个字符相等，同时比较插入到S后的结果与插入到T中的结果，取小的，如dp[i][j] = min{ dp[i][j-1] + 1, dp[i-1][j] + 1 }
3.第二步的三种不相等情况综合结果，再取最小值就是本次处理不相等的情况，dp[i][j] = min{ dp[i-1][j-1] + 1, dp[i-1][j] + 1, dp[i][j-1] + 1 }
代码实现
利用for循环把递归思路转化为非递归思路,重点理解for循环迭代实现了递归中的思路，注意for循环中的全部步骤为什么可以覆盖这个问题的全部情况
public static int similarityString(String s, String t) {
if(sLen == 0) return tLen;
if(tLen == 0) return sLen;
int sLen = s.length();
int tLen = t.length();
int i,j;
char ch1,ch2;
int cost;
int[][] dp = new int[sLen + 1][tLen + 1];
//下面两个是边界条件
for(i = 0; i <= sLen; i++) dp[i][0] = i; //这里是有意义的，就是当一个字符串长度为0，这就意味着另外一个字符串必须全部删除
for(i = 0; i <= tLen; i++) dp[0][i] = i ;
for(i = 1; i < = sLen; i++) { //第一个for循环表示第一个字符串取其前i个字符
ch1 = s.charAt(i - 1);
for(j = 1; j <= tLen; j++) { // 第二个for循环表示第二个字符串取其前j个字符
ch2 = t.charAt(j - 1);
if(ch1 == ch2) cost = 0;
else cost = 1;
dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1),dp[i - 1][j - 1] + cost);
}
}
return dp[sLen][tLen];
}
7. 最长公共子序列(Longest Common Subsequence,LCS)
问题描述
对于序列S和T，求它们的最长公共子序列的长度。例如X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}则它们的lcs是{B,C,B,A}和{B,D,A,B}，所以结果为4.
题目分析
dp[i][j] 表示取字符串S的第i个字符之前的序列和T的第j个字符之前的序列进行比对，求其最长子序列的长度。
1.从尾部字符开始取起，如果S和T字符串的字符相等，则dp[i][j] = dp[i-1][j-1] + 1.
2.如果S和T字符串的字符不相等，则比较以下两种情况，取其中的最大值
(a)留下S的字符，去掉T的字符，利用S当前字符与T的第j-1字符进行比较，dp[i][j] = dp[i][j-1]
(b)去掉S的字符，留下T的字符，利用S的前一个字符i-1字符与T的当前j字符进行比较，dp[i][j] = dp[i-1][j]
3.每进行一次取元素的时候，遇到的问题又与上一次遇到的情况是一样的，所以递归就可以实现。
代码实现
public static int compute(char[] str1, char[] str2){
int substringLength1 = str1.length;
int substringLength2 = str2.length;
// 构造二维数组记录子问题A[i]和B[j]的LCS的长度
int[][] dp = new int[substringLength1 + 1][substringLength2 + 1];
// 从后向前，动态规划计算所有子问题。也可从前到后。
for (int i = substringLength1 - 1; i >= 0; i--){
for (int j = substringLength2 - 1; j >= 0; j--){
if (str1[i] == str2[j])
dp[i][j] = dp[i + 1][j + 1] + 1;// 状态转移方程
else
//索引加的不同，表示参考基准不同
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]);// 状态转移方程
}
}
System.out.println("substring1:" + new String(str1));
System.out.println("substring2:" + new String(str2));
System.out.print("LCS:");
int i = 0, j = 0;
while (i < substringLength1 && j < substringLength2){
if (str1[i] == str2[j]){
System.out.print(str1[i]); //逐个输出最长公共子串
i++; j++;
}
else if (dp[i + 1][j] >= dp[i][j + 1]) i++;
else j++;
}
System.out.println();
return dp[0][0]; //最长公共子串的长度
}
8. Maximal Square
题目描述
给定一个只包含0和1的矩阵，找到只包含1的最大方阵并返回其面积。
例如，给出以下矩阵：
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
返回4。
题目分析
初始化另一个矩阵（dp），其尺寸与初始化为0的所有矩阵相同。
dp（i，j）表示右下角是原始矩阵中索引为（i，j）的单元格的最大方格的边长。
从索引（0,0）开始，对于在原始矩阵中找到的每个1元素，我们将当前元素的值更新为
代码实现
public class Solution {
public int maximalSquare(char[][] matrix) {
int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
int[][] dp = new int[rows + 1][cols + 1];
int maxsqlen = 0;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
if (matrix[i-1][j-1] == '1'){
dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
maxsqlen = Math.max(maxsqlen, dp[i][j]);
}
}
}
return maxsqlen * maxsqlen;
}
}
9.House Robber
问题描述
假如你是一名专业的强盗，计划抢劫沿街的房屋。每间房屋都藏有一定数量的金钱，但是同一晚上有两间相邻的房屋被闯入，它将自动触发警报。
输入一个代表每个房屋的金额的非负整数列表，在没有触发警报的情况下，输出你抢劫的最高金额。
代码实现
class Solution {
public int rob(int[] nums){
if(nums.length == 0) return 0;
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(dp[0], nums[1]);
if(nums.length < 2) return dp[nums.length -1];
for(int i = 2; i < n; i++){
dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
}
return dp[n];
}
}
10.Maximum Subarray
问题描述
在数组中找到连续的子数组（至少包含一个数字），使这个子数组的总和最大。
例如，给定数组[-2,1,-3,4,-1,2,1,-5,4]，
连续子数组[4,-1,2,1]的最大sum = 6.
代码实现
public int maxSubArray(int[] A) {
int n = A.length;
int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
dp[0] = A[0];
int max = dp[0];
for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
11.Range Sum Query - Immutable
问题描述
给定一个整数数组NUMS，找到索引（i,j）之间的元素的总和，包括端值。
例：
给定nums = [-2，0，3，-5，2，-1]
sumRange（0，2） - > 1
sumRange（2，5） - > -1
sumRange（0，5） - > -3
注意：
- 这个数组不能改变。
- 可能会有很多次sumRange函数调用。
代码实现
public class NumArray {
private int[] sums; /dp数组
public NumArray(int[] nums) {
if(nums.length != 0){
sums = new int[nums.length];
sums[0] = nums[0];
for(int i=1; i<nums.length; i++){
sums[i] = nums[i] + sums[i-1];
}
}
}
public int sumRange(int i, int j) {
return i==0 ? sums[j] : sums[j]-sums[i-1];
}
}
12.Unique Substrings in Wraparound String
题目描述
将字符串s作为“abcdefghijklmnopqrstuvwxyz”的无限循环·字符串，因此s将如下所示：“... zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd ....”。
现有另一个字符串p，请找出有多少个唯一的非空子串p存在于字符串s中。
注意： p只包含小写英文字母，p的大小可能超过10000。
例1：
输入： “a”
输出： 1
说明：字符串“s”中只有字符串“a”的子串“s”。
例2：
输入： “cac”
输出： 2
说明：字符串s中有两个字符串“cac”的子字符串“a”，“c”。
例3：
输入： “zab”
输出： 6
说明：字符串s中的字符串“zab”有六个子字符串“z”，“a”，“b”，“za”，“ab”，“zab”。
本例的特别说明
本例其实是顺序组合问题，除了位置不变，还有不能任意取不相邻的元素组合在一起，这种组合就是简单的相加就可以实现总数了。
例如， 字符abcd的本例组合，a,b,c,d,ab,bc,cd,abc,bcd,abcd共10个，实际上sum = 1+2+3+4,有几个就是几个的加法运算。
代码实现
public class Solution {
public int findSubstringInWraproundString(String p) {
// count[i] is the maximum unique substring end with ith letter.
// 0 - 'a', 1 - 'b', ..., 25 - 'z'.
int[] count = new int[26]; //容量只有26的散列表，用于dp辅助数组，实现最优子问题
// store longest contiguous substring ends at current position.
int maxLengthCur = 0;
for (int i = 0; i < p.length(); i++) {
if (i > 0 && (p.charAt(i) - p.charAt(i - 1) == 1 || (p.charAt(i - 1) - p.charAt(i) == 25)))
maxLengthCur++;
else
maxLengthCur = 1;
int index = p.charAt(i) - 'a'; //判断当前字符是那个字母
count[index] = Math.max(count[index], maxLengthCur); //更新字符中的数据，如果连续字符越长，数字越大，例如abcdfe, abcdef，其中前面的e和f为1，而后面字符串的e和f为5和6
}
// Sum to get result
int sum = 0;
for (int i = 0; i < 26; i++) {
sum += count[i];
}
return sum;
}
}
13.Maximum Product Subarray
问题描述
在数组中找到连续的子数组（至少包含一个数字），使该数组中包含最大的产品（相乘为最大）。
例如，给定数组[2,3,-2,4]，则连续的子数组[2,3]具有最大的product = 2*3= 6。
给定数组[2,3,-2,-1],则连续的子数组为[2,3,-2,-1]，product = 12.
代码实现
public class Solution {
public int maxProduct(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int[] f = new int[A.length];
int[] g = new int[A.length]; //用来存储最小值，因为有可能有多个复数
f[0] = A[0];
g[0] = A[0];
int res = A[0];
for (int i = 1; i < A.length; i++) {
f[i] = Math.max(Math.max(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
g[i] = Math.min(Math.min(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
res = Math.max(res, f[i]);
}
return res;
}
}
空间复杂度更好的代码
int maxProduct(int A[], int n) {
// store the result that is the max we have found so far
int r = A[0];
// imax/imin stores the max/min product of
// subarray that ends with the current number A[i]
for (int i = 1, imax = r, imin = r; i < n; i++) {
// multiplied by a negative makes big number smaller, small number bigger
// so we redefine the extremums by swapping them
if (A[i] < 0)
swap(imax, imin);
// max/min product for the current number is either the current number itself
// or the max/min by the previous number times the current one
imax = max(A[i], imax * A[i]);
imin = min(A[i], imin * A[i]);
// the newly computed max value is a candidate for our global result
r = max(r, imax);
}
return r;
}
14.Unique Paths
题目描述
机器人位于一个m x n网格的左上角（在下图中标记为“start”）。
机器人只能随时向下或向右移动。机器人正在尝试到达网格的右下角（在下图中标记为“finish”）。
有多少可能的独特路径？
代码实现（O(n*m)空间复杂度）
标准的方式，计算每一个位置的信息，这种方式可以完整的记忆内容，但是如果不需要就浪费空间了
class Solution {
int uniquePaths(int m, int n) {
vector<vector<int> > path(m, vector<int> (n, 1));
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
path[i][j] = path[i - 1][j] + path[i][j - 1];
return path[m - 1][n - 1];
}
};
代码实现（O[min(n,m)]空间复杂度）
因为我们只要知道当前列或前一列的信息就够了
class Solution {
int uniquePaths(int m, int n) {
if (m > n) return uniquePaths(n, m);
vector<int> pre(m, 1);
vector<int> cur(m, 1);
for (int j = 1; j < n; j++) {
for (int i = 1; i < m; i++)
cur[i] = cur[i - 1] + pre[i];
swap(pre, cur);
}
return pre[m - 1];
}
};
15.Create Maximum Number
题目描述
给定两个长度数组m和n数字0-9代表两个数字。k <= m + n从两个数字中创建最大长度数。必须保留来自同一阵列的数字的相对顺序。返回k数字的数组。您应该尝试优化算法的时间和空间复杂性。
例1：
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
返回[9, 8, 6, 5, 3]
例2：
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
返回[6, 7, 6, 0, 4]
例3：
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
返回[9, 8, 9]
题目分析
本题的情况是从两个数组中找到子数组使结果顺序最大值，其实本题有点类似于归并排序问题，但是由于保持原来的顺序，并且从中只选取k个数据，所以特点又有点不一样。
代码实现
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int n = nums1.length;
int m = nums2.length;
int[] ans = new int[k];
//在两个数组中选择i个数据和k-i个数据，然后找出对应数组中的i个或k-i个最大顺序数据
for (int i = Math.max(0, k - m); i <= k && i <= n; ++i) {
int[] candidate = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
if (greater(candidate, 0, ans, 0)) ans = candidate;
}
return ans;
}
//合并从两个数组中选取数据，大的放入ans数组中，这也是因为归并排序为稳定排序的原因可以实现此算法
private int[] merge(int[] nums1, int[] nums2, int k) {
int[] ans = new int[k];
for (int i = 0, j = 0, r = 0; r < k; ++r)
ans[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
return ans;
}
//比较两个数组在相同索引位置上的值，那个大，[4,3,2,1]>[4,3,1,1]
public boolean greater(int[] nums1, int i, int[] nums2, int j) {
while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
i++;
j++;
}
return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
}
//选择数组中的k个最大数据，注意这里的k个要与数组的个数比对，如果k=数组长度，则全部取值，否则在当前索引后面的个数还大于k个的时候，我们先取最大值。
//比如，[3,4,6,1]取两个，则先取3，如果3当前的索引后面还有多余2个的数据，当前索引为0，后面还有3个，所以比较3和4，大的放入ans数组中，后面是4小于6，取6，此时ans=[6,]，后面只有一个数据了，所以不管多大，取值后ans=[6,1]
public int[] maxArray(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[k];
for (int i = 0, j = 0; i < n; ++i) {
while (n - i + j > k && j > 0 && ans[j - 1] < nums[i]) j--;
if (j < k) ans[j++] = nums[i];
}
return ans;
}
复杂度
在最坏的情况下，算法的时间复杂度为O((m + n）^ 3）
16.Longest Valid Parentheses
题目描述
给定一个只包含字符'('和')'的字符串，找出最长且有效的括号子字符串的长度。
"(()"最长的有效括号子字符串"()"长度= 2。
而)()())"最长的有效括号子字符串"()()"，其长度= 4。
代码实现
class Solution {
public int longestValidParentheses(String s) {
if(s.length() <= 0) return 0;
Stack<Integer> stack = new Stack<Integer>(); //保存'('的索引位置
int max = 0; //记录最大长度
int leftIndex = -1; //记录stack加入'('的初始位置
for(int i = 0; i < s.length(); ++i){
if(s.charAt(i) == '(') stack.push(i);
else{
if(stack.isEmpty()) leftIndex = i;//如果第一个字符为')'时，会出现前面为空的情况，例如")()'
else{
stack.pop(); //只要不为空，则必然之前压入了'('，先依次计算最近距离，然后继续弹出，看是否还有'('，则继续拿当前字符索引减去stack中的值
if(stack.isEmpty()) max = Math.max(max, i - leftIndex);//如果为空了，则只能减去保存在leftIndex中的值，因为那个是起点
else max = Math.max(max, i - stack.peek()); //如果不为空则，表示之前还有'('
}
}
}
return max;
}
}
参考文献
[1] leetcode 518. Coin Change 2
[2] 跳台阶
[4] 变态跳台阶
[5] java 动态规划策略原理及例题(很详细）
[6] 常见的动态规划问题分析与求解
