动态规划 ： 把大问题拆分成很多子问题，甚至子问题的子问题来求解，这些子问题并非全部相互独立，而是把所有子问题的求解都算作一次计算，最后把这些子问题的解输出来得到原始的解。每个子问题就好比数学上的三角函数的一个周期内的图像描述，每个子问题是有共通性的，如果把一个子问题可能的细节全部考虑到，其他周期都是在重复这个周期内的所有细节描述，仅仅是换了一个递推的参数而已，那么这个动态规划问题的通项小问题模板就找到了。
class Solution {
public int climbStairs(int n) {
// // 方法1 递归实现 超时不可以
// if(n == 1 ){return 1;}
// if(n==2) return 2;
// return climbStairs(n-1)+climbStairs(n-2);
/** 方法2 动态规划 dp算法
f(1) =1 f(2) =2;f(3) =3; f(4) =5; f(n) = f(n-1)+f(n-2);-----斐波那契数列
滚动数组思想 第一个数和第二个数相加等于第三个数，下一次的时候把第一个数抛弃掉，然后再前两个相加为第三个
0 0 1
0 1 1
1 1 2
1 2 3
2 3 5
*/
int pre1 = 0,pre2 =0,rank =1;
for(int i =1;i<=n;++i){ // 0不用考虑
pre1=pre2;
pre2 = rank;
rank = pre1+pre2;
}
return rank;
}
}
class Solution {
public int rob(int[] nums) {
/**
动态规划都是先找规律
偷第k个房间 num[k] + sum(k-2)
不偷第k 个房间 sum(k-1)
*/
if(nums.length ==0 || nums ==null){
return 0;
}
int len = nums.length;
if(len == 1){
return nums[0];
}
int[] dp = new int[len];
dp[0] =nums[0]; // 初始情况下，只有一家可以偷
dp[1] = Math.max(nums[0],nums[1]); // 有两家可以偷的时候，选最大的一家
for(int i =2;i<len;++i){
// 如果偷当前第i家，就是i-2家的加上第i家的；
// 不偷i家，就是i-1
dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[len-1]; // len-1 就是最后一家的索引，因为数组长度为len，最后的索引是i-1
}
}
class Solution {
public int rob(int[] nums) {
/**,
[1,2,31]
[1,2,3] [1] // 第一个被偷了
[1] [2,3,1] // 第一个没有被偷
将数组拆分成两个单排数组，如
*/
int n=nums.length;
if(n==1) return nums[0];
// 数组的截取函数 Arrays.copyOfRange(nums,0,n-1)) 第一个参数是需要截取的数组，第二个参数是起始位置，第三是终止位置，左闭右开，不包含n-1
// 字符串的截取函数 s.substring(0,2) 第二个参数是截取的长度
// 取这两种情况的最大值 [1,2,3] [1] [1] [2,3,1]
return Math.max(myRob(Arrays.copyOfRange(nums,0,n-1)),myRob(Arrays.copyOfRange(nums,1,n)));
}
private int myRob(int[] nums){
int pre =0;// 上一次偷到的
int cur = 0, tmp; //cur是当前偷到的结果，tmp是中间变量
for(int num : nums){
tmp = cur;
cur = Math.max(pre+num,cur);// 分别对应当前num被偷 pre+num, 不被偷 cur
pre= tmp;
}
return cur;
}
}?
class Solution {
public int minPathSum(int[][] grid) {
/**
V(xy) 坐标xy出当前位置的值
a=f(x-1,y)
b= f(x,y-1) 分别对应走到上面和左边到时候的值
f(x,y) = min(a,b) +v(xy)
*/
int row = grid.length;
int col = grid[0].length;
// 初始化第一行 行不动为0 列动
for(int i=1;i<col;++i){
grid[0][i] += grid[0][i-1]; // 叠加，当前元素等于前面元素的和 1 3 1 -> 1 4 5
}
// 初始化第一列 行动列不动
for(int j =1;j<row;++j){
grid[j][0] += grid[j-1][0];
}
// 寻找最小路径
for(int i =1;i<row;i++){
for(int j =1;j<col;++j){
int min = Math.min(grid[i-1][j],grid[i][j-1]); // 比较左边和上面的最小值
grid[i][j] += min; // 当前的最小值为本位置处的值加上上面或者左边的最小值
}
}
return grid[row-1][col-1];
}
}
class Solution {
public int uniquePaths(int m, int n) {
//动态规划
int[][] num = new int[m][n];
// 初始化第一行
for(int i =0;i<n;++i){
num[0][i] = 1;
}
// 初始化第一列
for(int j =0;j<m;++j){
num[j][0] =1;
}
for(int i=1;i<m;++i){
for(int j =1;j<n;++j){
num[i][j] = num[i][j-1]+num[i-1][j];
}
}
return num[m-1][n-1];
}
}?
?
class NumArray {
private int[] sums;
public NumArray(int[] nums) {
/**
本题是计算i~j之间索引的综合 ,可以拆分成 sum(j) - sum(i)
*/
int n = nums.length;
// 数组下标从0开始，开辟n+1个空间是为了方面sumrange的运算i为0开始，不需要做特殊处理
sums = new int[n+1];
for(int i =0;i<n;++i){
// sum[i+1] 计算的是0~i下标的累加和 sum[0] = 0
sums[i+1] =sums[i]+nums[i];
}
}
public int sumRange(int left, int right) {
// right+1 减去 left 实际上计算的是0~right 的累加和 到 left-1 的累加和
return sums[right+1] - sums[left];
}
}
?
?
?
?
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
/**
找动态数组的最小模型
A[i] -A[i-1] = A[i-1] - A[i-2]
A[i] A[i-1] A[i-2] 构成等差数列
*/
if(nums==null || nums.length==0) return 0;
int n = nums.length;
int[] dp = new int[n];
for(int i =2;i<n;++i){
if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2]){
dp[i] = dp[i-1] +1; // 此时满足等差数列的数组个数比上一个子区间多1
}
}
//因为递增子区间不一定以最后一个元素结尾，因此需要返回dp数组返回的累加和
// 因为1~4的构成等差 3~5 也构成等差，那么1~5 一定 一定构成等差 ，所以总的是和
int total =0;
for(int count:dp){
total += count;
}
return total;
}
}
?
class Solution {
public int integerBreak(int n) {
/**
动态规划
将i拆分成j和i-j的和，如果i-j 不继续分，乘积就是 j*(i-j)
继续拆分就是 j*dp[i-j]
j固定的时候 dp[i] = max(j*(i-j),j*dp[i-j]) j的取值范围是 1 ~ i-1 需要遍历所有的j取最大值
*/
int[] dp = new int[n+1]; // 取值范围取n+1 是为了方便下标取值，索引是0~n，dp[0] = 0；1~n是有效的
dp[1] = 1;
for(int i=2;i<=n;++i){ // 计算基本的
for(int j =1;j<i;++j){
// 要么分为 j *(i-j) 要么为j*dp[i-j]
dp[i] = Math.max(dp[i], Math.max( j*(i-j), j*dp[i-j] ));
}
}
return dp[n];
}
}
class Solution {
public int numSquares(int n) {
// 动态规划
List<Integer> sqrList = generateSquare(n); // 找出所有的完全平方数
int[] dp = new int[n+1];
for(int i =1;i<=n;++i){
int min = Integer.MAX_VALUE;
for(int square :sqrList){
if(i<square){
break;
}
min = Math.min(min,dp[i-square]+1);
}
dp[i] = min;
}
return dp[n];
}
private List<Integer> generateSquare(int n ){
List<Integer> sqrList = new ArrayList<>();
// 找出所有的完全平方数 1 4 9 16 25
// 3 5 7 9 等差数列
int diff = 3;
int square = 1;
while(square<=n){
sqrList.add(square);
square += diff;
diff +=2; // 差每次加2
}
return sqrList;
}
}
public int lengthOfLIS(int[] nums) {
// 动态规划
int n = nums.length;
int[] dp = new int[n];
for(int i =0;i<n;++i){
int max= 1; // 初始情况下递增子序列长度最小是1；
// 遍历找所有下标小于等于i的数，做比较找到尽可能多的严格递增子序列
for(int j =0;j<i;++j){
if(nums[i] > nums[j]){
// 找到了一个nums[i] 比前序转移方程dp[j] 的最大值还要大，就说明递增子序列可以扩容
max = Math.max(max,dp[j]+1);
}
}
// 每一趟小标小于等于i的子序列，都能找到以i为结尾下标的最大递增子序列长度
dp[i] =max;
}
// 最后遍历找到最大的dp[i]
// return Arrays.stream(dp).max().orElse(0); // 最后一个是没有最大值的话设置默认值
int res =0;
for (int i=0;i<n;++i){
res = Math.max(res,dp[i]);
}
return res;
}
}
class Solution {
public int findLongestChain(int[][] pairs) {
// 1 、 按当前数列升序排列
Arrays.sort(pairs,(a,b)->(a[0]-b[0]));
int n = pairs.length;
int[] dp = new int[n];
// 初始情况下，最少肯定有一对，把dp全部填充为左边界的最小值1
Arrays.fill(dp,1);
for(int i =1;i<n;++i){
for(int j =0;j<i;++j){
//如果前序数对的右边界小于当前数对的左边界，满足题意，可以扩容
if(pairs[j][1]<pairs[i][0]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
}
return Arrays.stream(dp).max().orElse(0); // 取数组的最大值，可以for循环来获取
}
}?
class Solution {
public int wiggleMaxLength(int[] nums) {
/**
摆动序列，即一升一降；应注意只有两个也是
*/
// 动态规划
int up =1,down =1;
for(int i =1;i<nums.length;++i){
// 只要碰不到下一个下跌，up的数值将永远原地踏步
if(nums[i]>nums[i-1]){ // 升
up = down+1;
}else if(nums[i] < nums[i-1]){ 、// 降
down =up+1;
}
}
return Math.max(up,down);
}
}
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
// 动态规划
// 长度最小为1，不考虑0
int m1 =text1.length(),n1 = text2.length();
// dp[i][j] 含义是text1的前i个字符[0,i) 和 text2 的前j个字符[0,j) 的最长公共子序列长度
int[][] dp = new int[m1+1][n1+1];
for(int i =1;i<=m1;++i){
for(int j=1;j<=n1;++j){
if(text1.charAt(i-1) == text2.charAt(j-1)){ // -1是为了对应索引
dp[i][j] = dp[i-1][j-1]+1; //相同就在前序的基础上+1
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[m1][n1];
}
}
class Solution {
public boolean canPartition(int[] nums) {
/**
0-1 背包的问题，有一个容量为n的背包，要用这个背包装下物品的价值最大，这些物品有属性体积w和价值v；
定义一个二维数组dp存储最大价值，其中dp[i][j] 表示前i件物品体积不超过j的情况下能达到的最大价值
设第i件物品的价值为w，体积为v，根据第i件物品是否添加到背包中，可以分为两种情况讨论：
1、第i件物品没有添加到背包，总体积不超过j的前i件物品的最大价值就是前i-1 的情况，即dp[i][j] = dp[i-1][j]
2、第i件物品添加到了背包中，dp[i][j] = dp[i-1][j-w] +v
综合：
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w]+v)
空间优化：
前i件物品的状态仅仅与前i-1件物品的状态有关，因此可以将dp定义为一维数组，其中dp[j] 既可以表示dp[i-1][j] 也可以表示
dp[i][j]
*/
int sum = generateArraysSum(nums);
if(sum %2 !=0) return false;
int target = sum /2;
boolean[] dp = new boolean[target+1];
dp[0] = true;
// 0-1 背包， 一个物品只能用一次
for(int num:nums){
// 从后先前遍历，先计算dp[i] 在计算dp[i-num]
for(int j =target;j>=num;--j){
dp[j] = dp[j] || dp[j-num] ;
}
}
return dp[target];
}
private int generateArraysSum(int[] nums){
int sum = 0 ;
for(int num:nums){
sum += num;
}
return sum;
}
}