写一个动态规划的算法
递归是从上往下的计算，递归中有大量的重复计算，以斐波那契为例
动态规划是子上往下的解决问题，先解决小数据量下的结果层层类推，解决大数据规模下的问题
动态规划的思路：将原问题拆解成若干的子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。
有时候自顶向下的思考问题很容易，动态规划首先自顶向下的思考问题，然后用子底向上的实现。
public int fib(int n){
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
memo[0] = 0;
memo[1] = 1;
for(int i = 2 ; i <= n ; i ++)
memo[i] = memo[i - 1] + memo[i - 2];
return memo[n];
}一个楼梯，总共有n阶台阶，每一次可以上一个台阶，也可以上两个台阶，爬上一个楼梯一共有多少个方法
递归树
public int climbStairs(int n) {
int[] memo = new int[n + 1];
memo[0] = 1;
memo[1] = 1;
for(int i = 2 ; i <= n ; i ++)
memo[i] = memo[i - 1] + memo[i - 2];
return memo[n];
}发现子问题
给定一个正数n，可以将其分隔成多个数字的和，若要这些数字的乘积最大，求分隔发放(至少要分成两个数)
递归树
public int integerBreak(int n) {
if(n < 1)
throw new IllegalArgumentException("n should be greater than zero");
memo = new int[n+1];
Arrays.fill(memo, -1);
return breakInteger(n);
}
// 将n进行分割(至少分割两部分), 可以获得的最大乘积
private int breakInteger(int n){
if(n == 1)
return 1;
if(memo[n] != -1)
return memo[n];
int res = -1;
for(int i = 1 ; i <= n - 1 ; i ++)
res = max3(res, i * (n - i) , i * breakInteger(n - i));
memo[n] = res;
return res;
}可以转化为求子问题的最优解，通过子问题的最优解可以获得原问题的最优解，知道了子问题的最优解就可以获得原问题的最优解。
只有同时满足重叠子问题与最优子结构(子问题的最优解，分隔n-1获得的最大乘积，分隔n-2一直到分隔1把答案综合起来)才能用动态规划解决。
知道了子问题的最优解就知道了原问题的最优解。
private int[] memo;
public int integerBreak(int n) {
if(n < 1)
throw new IllegalArgumentException("n should be greater than zero");
memo = new int[n+1];
Arrays.fill(memo, -1);
return breakInteger(n);
}
// 将n进行分割(至少分割两部分), 可以获得的最大乘积
private int breakInteger(int n){
if(n == 1)
return 1;
if(memo[n] != -1)
return memo[n];
int res = -1;
for(int i = 1 ; i <= n - 1 ; i ++)
res = max3(res, i * (n - i) , i * breakInteger(n - i));
memo[n] = res;
return res;
}
private int max3(int a, int b, int c){
return Math.max(a, Math.max(b, c));
}
状态的定义与状态的转义
一条街的房子，每个房子都有不同价值的宝物，不能拿连续两个放假的宝物，最多可以拿到的价值
拥有重叠子问题与最优子结构就可以使用动态规划
// memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
private int[] memo;
public int rob(int[] nums) {
memo = new int[nums.length];
Arrays.fill(memo, -1);
return tryRob(nums, 0);
}
// 考虑抢劫nums[index...nums.size())这个范围的所有房子
private int tryRob(int[] nums, int index){
if(index >= nums.length)
return 0;
if(memo[index] != -1)
return memo[index];
int res = 0;
for(int i = index ; i < nums.length ; i ++)
res = Math.max(res, nums[i] + tryRob(nums, i + 2));
memo[index] = res;
状态转移方程
状态定义函数要做什么，状态转移定义函数怎么做
// memo[i] 表示考虑抢劫 nums[0...i] 所能获得的最大收益
private int[] memo;
public int rob(int[] nums) {
memo = new int[nums.length];
Arrays.fill(memo, -1);
return tryRob(nums, nums.length - 1);
}
// 考虑抢劫nums[0...index]这个范围的所有房子
private int tryRob(int[] nums, int index){
if(index < 0)
return 0;
if(memo[index] != -1)
return memo[index];
int res = 0;
for(int i = 0 ; i <= index ; i ++)
res = Math.max(res, nums[i] + tryRob(nums, i - 2));
memo[index] = res;
return res;
}
public int rob(int[] nums) {
int n = nums.length;
if(n == 0)
return 0;
// memo[i] 表示考虑抢劫 nums[0...i] 所能获得的最大收益
int[] memo = new int[nums.length];
memo[0] = nums[0];
for(int i = 1 ; i < n ; i ++)
for (int j = i; j >= 0; j--)
memo[i] = Math.max(memo[i],
nums[j] + (j - 2 >= 0 ? memo[j - 2] : 0));
return memo[n-1];
}通过规模最小的解推出规模最大的解，最后求带mem[0]是整个问题的整体
public int rob(int[] nums) {
int n = nums.length;
if(n == 0)
return 0;
// memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
int[] memo = new int[nums.length];
memo[n - 1] = nums[n - 1];
for(int i = n - 2 ; i >= 0 ; i --)
for (int j = i; j < n; j++)
memo[i] = Math.max( memo[i],
nums[j] + (j + 2 < n ? memo[j + 2] : 0));
return memo[0];
}动态规划的经典0-1背包问题
问题的实质对于第i个物品是要放进背包还是不放进背包
n-1为考虑物品截止位置的索引，index-1考虑从0到index-1这么多物品填充容积为C的背包的价值是多少，另外一种策略选择index的物品看一共的价值是多少。
同样的数据对有可能出现多次，背包问题有两个约束条件，每一个状态有两种约束条件，开辟记忆化空间为二维数组
private int[][] memo;
public int knapsack01(int[] w, int[] v, int C){
if(w == null || v == null || w.length != v.length)
throw new IllegalArgumentException("Invalid w or v");
if(C < 0)
throw new IllegalArgumentException("C must be greater or equal to zero.");
int n = w.length;
if(n == 0 || C == 0)
return 0;
memo = new int[n][C + 1];
for(int i = 0; i < n; i ++)
for(int j = 0; j <= C; j ++)
memo[i][j] = -1;
return bestValue(w, v, n - 1, C);
}
// 用 [0...index]的物品,填充容积为c的背包的最大价值
private int bestValue(int[] w, int[] v, int index, int c){
if(c <= 0 || index < 0)
return 0;
if(memo[index][c] != -1)
return memo[index][c];
int res = bestValue(w, v, index-1, c);
if(c >= w[index])
res = Math.max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));
return memo[index][c] = res;
}
动态规划
3行表示3个物品，6列表示0-5相应的6列填充背包的容量为0-5，[2，5]就是所要的结果
第二行考虑0.1两个物品，基于考虑9物品得到的答案
public int knapsack01(int[] w, int[] v, int C){
if(w == null || v == null || w.length != v.length)
throw new IllegalArgumentException("Invalid w or v");
if(C < 0)
throw new IllegalArgumentException("C must be greater or equal to zero.");
int n = w.length;
if(n == 0 || C == 0)
return 0;
int[][] memo = new int[n][C + 1];
for(int j = 0 ; j <= C ; j ++)
memo[0][j] = (j >= w[0] ? v[0] : 0 );
for(int i = 1 ; i < n ; i ++)
for(int j = 0 ; j <= C ; j ++){
memo[i][j] = memo[i-1][j];
if(j >= w[i])
memo[i][j] = Math.max(memo[i][j], v[i] + memo[i - 1][j - w[i]]);
}
return memo[n - 1][C];
}0-1背包的空间优化
第i-1行的内容只依赖i-1行的内容，不依赖i-1行之前的元素是什么样子
只用考虑奇偶，物理空间只有两行了
public int knapsack01(int[] w, int[] v, int C){
if(w == null || v == null || w.length != v.length)
throw new IllegalArgumentException("Invalid w or v");
if(C < 0)
throw new IllegalArgumentException("C must be greater or equal to zero.");
int n = w.length;
if(n == 0 || C == 0)
return 0;
int[][] memo = new int[2][C + 1];
for(int j = 0 ; j <= C ; j ++)
memo[0][j] = (j >= w[0] ? v[0] : 0);
for(int i = 1 ; i < n ; i ++)
for(int j = 0 ; j <= C ; j ++){
memo[i % 2][j] = memo[(i-1) % 2][j];
if(j >= w[i])
memo[i % 2][j] = Math.max(memo[i % 2][j], v[i] + memo[(i-1) % 2][j - w[i]]);
}
return memo[(n-1) % 2][C];
}只使用一行，考虑i=1的这一行，因为容量是2所以考虑5-2等于3的位置
public int knapsack01(int[] w, int[] v, int C){
if(w == null || v == null || w.length != v.length)
throw new IllegalArgumentException("Invalid w or v");
if(C < 0)
throw new IllegalArgumentException("C must be greater or equal to zero.");
int n = w.length;
if(n == 0 || C == 0)
return 0;
int[] memo = new int[C+1];
for(int j = 0 ; j <= C ; j ++)
memo[j] = (j >= w[0] ? v[0] : 0);
for(int i = 1 ; i < n ; i ++)
for(int j = C ; j >= w[i] ; j --)
memo[j] = Math.max(memo[j], v[i] + memo[j - w[i]]);
return memo[C];
}非空数组，所有的数字都是正整数，可以将数组的元素分为两部分，每部分数字和相等
状态转移方程
// memo[i][c] 表示使用索引为[0...i]的这些元素,是否可以完全填充一个容量为c的背包
// -1 表示为未计算; 0 表示不可以填充; 1 表示可以填充
private int[][] memo;
public boolean canPartition(int[] nums) {
int sum = 0;
for(int i = 0 ; i < nums.length ; i ++){
if(nums[i] <= 0)
throw new IllegalArgumentException("numbers in nums must be greater than zero.");
sum += nums[i];
}
if(sum % 2 == 1)
return false;
memo = new int[nums.length][sum / 2 + 1];
for(int i = 0 ; i < nums.length ; i ++)
Arrays.fill(memo[i], -1);
return tryPartition(nums, nums.length - 1, sum / 2);
}
// 使用nums[0...index], 是否可以完全填充一个容量为sum的背包
private boolean tryPartition(int[] nums, int index, int sum){
if(sum == 0)
return true;
if(sum < 0 || index < 0)
return false;
if(memo[index][sum] != -1)
return memo[index][sum] == 1;
memo[index][sum] = (tryPartition(nums, index - 1, sum) ||
tryPartition(nums, index - 1, sum - nums[index])) ? 1 : 0;
return memo[index][sum] == 1;
}
动态规划
初始化的时候，判断nums[i]是否为背包的容量i吗，如果等于扔进去填满背包
状态转移的双重循环解决问题，每一次多考虑一个数，从容量C开始到这往前推，看使用第i个新的物品能不能被填满
public boolean canPartition(int[] nums) {
int sum = 0;
for(int i = 0 ; i < nums.length ; i ++){
if(nums[i] <= 0)
throw new IllegalArgumentException("numbers in nums must be greater than zero.");
sum += nums[i];
}
if(sum % 2 == 1)
return false;
int n = nums.length;
int C = sum / 2;
boolean[] memo = new boolean[C + 1];
for(int i = 0 ; i <= C ; i ++)
memo[i] = (nums[0] == i);
for(int i = 1 ; i < n ; i ++)
for(int j = C; j >= nums[i] ; j --)
memo[j] = memo[j] || memo[j - nums[i]];
return memo[C];
}给定一个整数，求其中最长的上升子序列的长度
private int[] memo;
public int lengthOfLIS(int[] nums) {
if(nums.length == 0)
return 0;
memo = new int[nums.length];
Arrays.fill(memo, -1);
int res = 1;
for(int i = 0 ; i < nums.length ; i ++)
res = Math.max(res, getMaxLength(nums, i));
return res;
}
// 以 nums[index] 为结尾的最长上升子序列的长度
private int getMaxLength(int[] nums, int index){
if(memo[index] != -1)
return memo[index];
int res = 1;
for(int i = 0 ; i <= index-1 ; i ++)
if(nums[index] > nums[i])
res = Math.max(res, 1 + getMaxLength(nums, i));
return memo[index] = res;
}
状态转移方程的逻辑，如果求i的最长子序列，找i之前的所有的元素，如果发现某一个num[i]比之前的num[j]大又获得一个新的上升子序列，加上LIS（j） 以j结尾的上升子序列
一开始只考虑自己为长度为1的上升子序列，当前面的上升子序列求出来后面的子序列也可以求出来
public int lengthOfLIS(int[] nums) {
if(nums.length == 0)
return 0;
// memo[i] 表示以 nums[i] 为结尾的最长上升子序列的长度
int memo[] = new int[nums.length];
Arrays.fill(memo, 1);
for(int i = 1 ; i < nums.length ; i ++)
for(int j = 0 ; j < i ; j ++)
if(nums[i] > nums[j])
memo[i] = Math.max(memo[i], 1 + memo[j]);
int res = memo[0];
for(int i = 1 ; i < nums.length ; i ++)
res = Math.max(res, memo[i]);
return res;
}给出两个字符串S1和S2，求两个字符串的最长公共子序列
处理字符串问题的状态转移方程，如果字符相等则为1+LCS(m-1，n-1)，如果字符不相等，则往前缩一位进行比较
public String lcs(String s1, String s2){
int m = s1.length();
int n = s2.length();
// 对memo的第0行和第0列进行初始化
int[][] memo = new int[m][n];
for(int j = 0 ; j < n ; j ++)
if(s1.charAt(0) == s2.charAt(j)){
for(int k = j ; k < n ; k ++)
memo[0][k] = 1;
break;
}
for(int i = 0 ; i < m ; i ++)
if(s1.charAt(i) == s2.charAt(0)) {
for(int k = i ; k < m ; k ++)
memo[k][0] = 1;
break;
}
// 动态规划的过程
for(int i = 1 ; i < m ; i ++)
for(int j = 1 ; j < n ; j ++)
if(s1.charAt(i) == s2.charAt(j))
memo[i][j] = 1 + memo[i-1][j-1];
else
memo[i][j] = Math.max(memo[i-1][j], memo[i][j-1]);
// 通过memo反向求解s1和s2的最长公共子序列
m = s1.length() - 1;
n = s2.length() - 1;
StringBuilder res = new StringBuilder("");
while(m >= 0 && n >= 0)
if(s1.charAt(m) == s2.charAt(n)){
res.insert(0, s1.charAt(m));
m --;
n --;
}
else if(m == 0)
n --;
else if(n == 0)
m --;
else{
if(memo[m-1][n] > memo[m][n-1])
m --;
else
n --;
}
return res.toString();
}动态规划与贪心算法的关系
通常贪心算法代码会非常的段而且思路很清晰，但是贪心算法难点在于确定可以使用贪心算法能解决。
给小朋友送饼干，每个小朋友能得到一块饼干，每个饼干有一个大小值s(i)，每个学生有一个贪心指数g(i)，必须s(i)要大于g(i)
如果当前最大的饼干都无法满足最贪心的小朋友说明所有的都无法满足，每次尝试使用剩下最大的饼干，最大程度保证所有小朋友都开心
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int gi = g.length - 1, si = s.length - 1;
int res = 0;
while(gi >= 0 && si >= 0){
if(s[si] >= g[gi]){
res ++;
si --;
}
gi --;
}
return res;
}public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int gi = 0, si = 0;
int res = 0;
while(gi < g.length && si < s.length){
if(s[si] >= g[gi]){
res ++;
gi ++;
}
si ++;
}
return res;
}贪心算法与动态规划
给定一组区间，问最少删除多少个区间，让这些区间之间互相不重叠
与最长上升子区间的比较，每一次根前面区间的后面比较，然后+1
先排序才能判断不重叠
// Definition for an interval.
public static class Interval {
int start;
int end;
Interval() { start = 0; end = 0; }
Interval(int s, int e) { start = s; end = e; }
}
public int eraseOverlapIntervals(Interval[] intervals) {
if(intervals.length == 0)
return 0;
Arrays.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
if(o1.start != o2.start)
return o1.start - o2.start;
return o1.end - o2.end;
}
});
// memo[i]表示以intervals[i]为结尾的区间能构成的最长不重叠区间序列
int[] memo = new int[intervals.length];
Arrays.fill(memo, 1);
for(int i = 1 ; i < intervals.length ; i ++)
// memo[i]
for(int j = 0 ; j < i ; j ++)
if(intervals[i].start >= intervals[j].end)
memo[i] = Math.max(memo[i], 1 + memo[j]);
int res = 0;
for(int i = 0; i < memo.length ; i ++)
res = Math.max(res, memo[i]);
return intervals.length - res;
}