动态规划算法和回溯算法很像，需要明确basecase、状态、选择。
动态规划的暴力穷举求解阶段就是回溯算法。只是有的问题可以构造最优子结构，找到重叠子问题，可以用dp table优化，将递归树大幅剪枝。
一方面，动态规划问题的一般形式就是求最值。核心是穷举，但其存在“重叠子问题”，如果暴力穷举效率会极其低下，所以需要使用dp数组来优化穷举过程，避免不必要的计算。
另一方面，动态规划问题一定会具备“最优子结构”（子问题必须相互独立），这样才能通过子问题的最值得到原问题的最值。
最后，只有列出正确的“状态转移方程”，才能正确的穷举。写出正确的状态转移方程，一定要思考basecase、状态、选择、dp数组的定义（表示状态和选择）
思考的流程：
自顶向下的递归 （已经需要basecase、状态、选择。“状态”用函数参数存储，“选择”需要遍历）
-》 自顶向下的递归+备忘录（空间换时间）
-》 自下向上的循环+dp数组（和自顶向下复杂度差不多，状态用dp数组下标存储）
-》 dp数组的缩小（状态压缩）
例题1：斐波那契数列
class Solution {
public int fib(int n) {
int[] dp=new int[n+1];
dp[0]=0;
if(n==0){
return 0;
}
dp[1]=1;
for(int i=2;i<=n;++i){
dp[i]=(dp[i-1]+dp[i-2])%1000000007;
}
return dp[n];
}
}
状态压缩后：
class Solution {
public int fib(int n) {
int dp1=0,dp2=1;
if(n==0||n==1){
return n;
}
for(int i=2;i<=n;++i){
int temp=(dp1+dp2)%1000000007;
dp1=dp2;
dp2=temp;
}
return dp2;
}
}
一、01背包
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
int n=in.nextInt();
int V=in.nextInt();
int[] v=new int[n+1]; //volume体积
int[] c=new int[n+1]; //cost价值
for(int i=0;i=v[i];--j){
dp[j]= Math.max(dp[j],dp[j-v[i]]+c[i]);
}
}
System.out.println(dp[V]);
}
//若背包恰好装满，求至多能装多大价值的物品。dp[i][v]表示前i个物品 恰好 装入容量为v的背包中能获得最大价值。就是初始化的不一样。
static void justF(int n,int V,int[] v,int[] c){
int[] dp=new int[V+1];
Arrays.fill(dp,Integer.MIN_VALUE);
dp[0]=0;
for(int i=1;i<=n;++i){
for(int j=V;j>=v[i];--j){
dp[j]= Math.max(dp[j],dp[j-v[i]]+c[i]);
}
}
int result=dp[V]<0?0:dp[V];
System.out.println(result);
}
}
例题1： 分割等和子集
例题2： 一和零
例题3： 目标和
解法1：回溯算法
时间复杂度太高
class Solution {
int count=0;
public int findTargetSumWays(int[] nums, int target) {
dfs(nums,0,target,0);
return count;
}
void dfs(int[] nums,int index,int target,int sum){
if(index>=nums.length){
if(sum==target){
++count;
}
return;
}
dfs(nums,index+1,target,sum+nums[index]);
dfs(nums,index+1,target,sum-nums[index]);
}
}
解法2：动态规划算法
1 我们要消除target可能为负数的影响，所以要进行转换，将原题变为01背包问题，而不是现在的这个-11背包问题
这里实际上找的是nums[]选哪些数字可以让其和为(sum-target)/2，推导如下：
设被减去的数字和为neg，所有数字和为sum。有sum-2neg=target，则neg=(sum-target)/2
2 由于 nums[i]可以等于0 ，而且+0，-0算两种方法，所以不能让dp[i][0]都为1，而只能让dp[0][0]为1
class Solution {
public int findTargetSumWays(int[] nums, int target) {
//真正的目标数字realTarget，这样才是01背包问题
int sum=0;
for(int i=0;i=nums[i-1]){
dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
}else{
dp[i][j]=dp[i-1][j];
}
}
}
return dp[dp.length-1][dp[0].length-1];
}
}
例题4： 盈利计划
例题5： 最后一块石头的重量 II
二、完全背包
大佬题解中的程序猿大队长
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
int n=in.nextInt();
int V=in.nextInt();
int[] v=new int[n+1]; //volume体积
int[] c=new int[n+1]; //cost价值
for(int i=0;i
例题1： 数位成本和为目标值的最大数字
例题2：零钱兑换
贪心是不行的，比如coins=[1,51,100]，target=102用贪心就是错的
状态是目标金额（dp的下标），所需结果是目标金额的最少硬币数（dp的内容），选择是每种硬币的面值
class Solution {
public int coinChange(int[] coins, int amount) {
//dp下标表示状态：目标金额；dp内容需要的最少硬币个数
int[] dp=new int[amount+1];
//初始化base case（基本情况）
dp[0]=0;
for(int i=1;i<=amount;++i){
dp[i]=(amount+1);
}
//i用来遍历状态
for(int i=1;i<=amount;++i){
//coin用来遍历选择
for(int coin:coins){
int temp=i-coin;
if(temp<0){
continue;
}
dp[i]=Math.min(dp[temp]+1,dp[i]);
}
}
return dp[amount]==(amount+1)?-1:dp[amount];
}
}
例题3：零钱兑换 II
例题4：完全平方数
三、分组背包
例题1：掷骰子的N种方法
四、其他
例题1：最长回文子串
很明显求解出所有的字符串自然能够找到最大的，与例题2做好比较。大佬题解
解法1：动态规划法
class Solution {
public String longestPalindrome(String s) {
boolean[][] dp=new boolean[s.length()][s.length()];
int left=-1,right=-2;
for(int j=0;j
解法2：中心扩散双指针
class Solution {
public String longestPalindrome(String s) {
int needLeft=-1,needRight=-2;
for (int center = 0; center< 2*s.length()-1; center++) {
int left=center/2;
int right=left+center%2;
while(left>=0&&rightneedRight-needLeft){
needRight=right;
needLeft=left;
}
--left;
++right;
}
}
return s.substring(needLeft,needRight+1);
}
}
例题2：回文子串
大佬题解
解法1：动态规划法
状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。
class Solution {
public int countSubstrings(String s) {
// 动态规划
boolean[][] dp = new boolean[s.length()][s.length()];
int result = 0;
for (int j = 0; j < s.length(); j++) { //一定要把列放在外层
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
result++;
}
}
}
return result;
}
}
解法2：中心扩散双指针
class Solution {
public int countSubstrings(String s) {
int result = 0;
for (int center = 0; center< 2*s.length()-1; center++) {
int left=center/2;
int right=left+center%2;
while(left>=0&&right
例题3：最少回文分割
dp[i]的含义为字符串长度从0到i,最少可以分为几个回文串
class Solution {
public int minCut(String s) {
int n = s.length();
int[] dp = new int[n+1];
dp[0]=0;
for(int i=1;i<=n;i++){
dp[i]=i;
for(int j=0;j
例题4：连续子数组的最大和
状态：dp[i]表示以A[i]作为末尾的连续序列的最大和。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
while(in.hasNextInt()){
int n=in.nextInt();
int[] arr=new int[n];
for(int i=0;i
例题5：最长上升子序列
给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。
解法1：动态规划
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] arr=new int[n];
for(int i=0;idp[i]){
dp[i]=dp[j]+1;
}
}
result=Math.max(result,dp[i]);
}
System.out.println(result);
}
}
解法2：动态规划+二分搜索算法
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] arr=new int[n];
for(int i=0;i value[maxLength]) {
// 大于目前最大长度的子序列的最后一位，给value[]后边续上
maxLength++;
value[maxLength] = arr[i];
} else {
// 小于目前最大长度的子序列的最后一位，查找前边部分第一个大于自身的位置
// 更新它
int t = find(value, maxLength, arr[i]);
value[t] = arr[i];
}
}
System.out.println(maxLength);
}
// 二分查找
private static int find(int[] value, int maxindex, int i) {
int l = 1, r = maxindex;
while (l <= r) {
int mid = (l + r) / 2;
if (i > value[mid]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return l;
}
}
例题6：最长上升子序列扩展
小强现在有个物品,每个物品有两种属性和.他想要从中挑出尽可能多的物品满足以下条件:对于任意两个物品和,满足或者.问最多能挑出多少物品.
输入例子1:
2
3
1 3 2
0 2 3
4
1 5 4 2
10 32 19 21
输出例子1:
2
3
import java.util.*;
class Node implements Comparable{ //不能直接在Arrays.sort()里面用lamda函数,会超时。必须要类实现Comparable接口，重写compareTo()
int x;
int y;
public Node(int x,int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Object o) {
Node node = (Node) o;
return this.x==node.x?node.y-this.y:this.x-node.x;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
for (int i = 0; i < num; i++) {
int goodsNum = sc.nextInt();
int[] linearr1 = new int[goodsNum];
int[] linearr2 = new int[goodsNum];
for (int j = 0; j < linearr1.length; j++) {
linearr1[j] = sc.nextInt();
}
for (int j = 0; j < linearr2.length; j++) {
linearr2[j] = sc.nextInt();
}
Node[] list = new Node[goodsNum];
for (int j = 0; j < list.length; j++) {
list[j] = new Node(linearr1[j], linearr2[j]);
}
Arrays.sort(list);
//动态规划+二分法
binarySearch(list);
}
}
private static void binarySearch(Node[] arr) {
int[] value = new int[arr.length +1];
int maxLength = 1;
value[1] = arr[0].y;
for (int i = 1; i < arr.length; i++) {
if (arr[i].y > value[maxLength]) {
value[++maxLength] = arr[i].y;
} else {
int t = find(value, maxLength, arr[i].y);
value[t] = arr[i].y;
}
}
System.out.println(maxLength);
}
// 二分查找
private static int find(int[] value, int maxindex, int i) {
int l = 1, r = maxindex;
while (l <= r) {
int mid = (l + r) / 2;
if (i > value[mid]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return l;
}
}
例题7：最长上升子序列扩展
解法1：动态规划
空间复杂度 O(mn)，时间复杂度 O(mn)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
int n=in.nextInt();
int m=in.nextInt();
String a=in.next();
String b=in.next();
//逻辑开始
int[][] dp=new int[n+1][m+1];
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(a.charAt(i-1)==b.charAt(j-1)){
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(dp[n][m]);
}
}
解法2：优化空间复杂度
空间复杂度 O(min(m,n))，时间复杂度 O(mn)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
int n=in.nextInt();
int m=in.nextInt();
String a=in.next();
String b=in.next();
//逻辑开始
if(n
例题8：DAG最长路
DAG是有向无环图。
（1）求整个DAG中的最长路径
dp[i]表示从i号顶点出发能获得的最长路径长度。图用邻接矩阵存储。
class Solution {
int DP(int i){
if(dp[i]>0)return dp[i];
for(int j=0;jdp[i]){ //可以获得更长的路径
dp[i]=temp; //覆盖dp[i]
choice[i]=j; //i号顶点的后继顶点是j
}
}
}
return dp[i];
}
//调用printPath前需要先得到最大的dp[i]，然后将i作为路径起点传入
void printPath(int i){
System.out.print(i);
while(choice[i]!=-1){ //choice数组初始化为-1
i=choice[i];
System.out.println("->"+i);
}
}
}
（2）固定终点，求DAG的最长路径
dp[i]表示从i号顶点出发到达重点T能获得的最长路径长度。图用邻接矩阵存储。
class Solution {
int DP(int i){
if(vis[i])return dp[i];
vis[i]=true;
for(int j=0;j
例题9：数塔问题
import java.util.*;
public class T5 {
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
int n=in.nextInt();
int[][] num=new int[n+1][n+1];
int[][] dp=new int[n+1][n+1];
for(int i=1;i<=n;++i){
for(int j=1;j<=i;++j){
num[i][j]=in.nextInt();
}
}
//逻辑开始
for(int j=1;j<=n;++j){
dp[n][j]=num[n][j];
}
for(int i=n-1;i>=1;--i){
for(int j=1;j<=i;++j){
dp[i][j]=Math.max(dp[i+1][j],dp[i+1][j+1])+num[i][j];
}
}
System.out.println(dp[1][1]);
}
}
例题10：二叉树方案数
import java.util.*;
public class T9 {
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
int n=in.nextInt();
int m=in.nextInt();
//逻辑开始
//[i][j]表示i个节点最大深度为j的树数量
int mod= (int)Math.pow(10,9)+7;
long[][] dp=new long[n+1][m+1]; //必须是long，不然只能通过部分用例
Arrays.fill(dp[0], 1);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
for(int k=0;k
例题11：正确比例下的最大乘积
