动态规划 - 《算法技巧》

1 想法
2 应用与例题
- 1斐波那契数列
  - 斐波那契数">1 斐波那契数
  - 2 爬楼梯
- 2 完全平方数
  - 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
3最小路径和
- 思路
4 不同路径
最长上升子序列">5 最长上升子序列
整数拆分">6 整数拆分
背包问题

1 想法

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

想法1

1确定状态
最后一步
子问题
2 状态转移方程
3 初始条件，边界条件
计算顺序：利用计算结果，减少重复计算

想法2

刻画一个最优解的结构特征
递归地定义最优解的值
计算最优解的值，通常采用自低向上
利用计算出的信息构造一个最优解

想法3：从集合的角度来思考dp;

1 状态
集合：
属性：
2 状态计算-集合的划分

想法4

怎么鉴定dp可解的一类问题需要从计算机是怎么工作的说起…计算机的本质是一个状态机，内存里存储的所有数据构成了当前的状态，CPU只能利用当前的状态计算出下一个状态（不要纠结硬盘之类的外部存储，就算考虑他们也只是扩大了状态的存储容量而已，并不能改变下一个状态只能从当前状态计算出来这一条铁律）
当你企图使用计算机解决一个问题是，其实就是在思考如何将这个问题表达成状态（用哪些变量存储哪些数据）以及如何在状态中转移（怎样根据一些变量计算出另一些变量）。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少，所谓时间复杂度就是从初始状态到达最终状态中间需要多少步！

每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到这个性质叫做最优子结构；而不管之前这个状态是如何得到的这个性质叫做无后效性。

想法5

动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
核心: 如何拆分问题
拆分问题，靠的就是状态的定义和状态转移方程的定义。

什么是状态的定义？

给定一个数列，长度为N，求这个数列的最长上升（递增）子数列（LIS）的长度.以1 7 2 8 3 4为例。这个数列的最长递增子数列是 1 2 3 4，长度为4；次长的长度为3，包括 1 7 8; 1 2 3 等.

要解决这个问题，我们首先要定义这个问题和这个问题的子问题。
重新定义这个问题：给定一个数列，长度为N，设> 为：以数列中第k项结尾的最长递增子序列的长度.求> 中的最大值.>
显然，这个新问题与原问题等价。
而对于来讲，都是的子问题：因为以第k项结尾的最长递增子序列（下称LIS），包含着以第中某项结尾的LIS。
上述的新问题也可以叫做状态，定义中的“为数列中第k项结尾的LIS的长度”，就叫做对状态的定义。
之所以把做“状态”而不是“问题” ，一是因为避免跟原问题中“问题”混淆，二是因为这个新问题是数学化定义的。

对状态的定义只有一种吗？当然不是。

以二维的，以完全不同的视角定义这个问题：给定一个数列，长度为N，设> 为：在前i项中的，长度为k的最长递增子序列中，最后一位的最小值. > .若在前i项中，不存在长度为k的最长递增子序列，则> 为正无穷.求最大的x，使得> 不为正无穷。

上述的动态规划 - 图14 就是状态，定义中的“ 动态规划 - 图15 为：在前i项中，长度为k的最长递增子序列中，最后一位的最小值”就是对状态的定义。

什么是状态转移方程？
上述状态定义好之后，状态和状态之间的关系式，就叫做状态转移方程。
比如，对于LIS问题，我们的第一种定义：设> 为：以数列中第k项结尾的最长递增子序列的长度.

设A为题中数列，状态转移方程为：

（根据状态定义导出边界情况）> >

以第k项结尾的LIS的长度是：保证第i项比第k项小的情况下，以第i项结尾的LIS长度加一的最大值，取遍i的所有值（i小于k）。

第二种定义：设> 动态规划 - 图20 为：在数列前i项中，长度为k的递增子序列中，最后一位的最小值设A为题中数列，状态转移方程为：若> 动态规划 - 图21 则> 动态规划 - 图22 否则：> 动态规划 - 图23 （边界情况需要分类讨论较多）
大家套着定义读一下公式就可以了，应该不难理解，就是有点绕。
这里可以看出，这里的状态转移方程，就是定义了问题和子问题之间的关系。
可以看出，状态转移方程就是带有条件的递推式。

2 应用与例题

1斐波那契数列

1 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。

示例 1：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

idea: 注意前两个数的边界条件。

class Solution {
    public int fib(int N) {
     if( N <=1){
            return N;
        }
        int[] dp = new int[N+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i<=N; i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[N];
    }
}

2 爬楼梯

70. Climbing Stairs (Easy)
题目描述：有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。
定义一个数组 dp 存储上楼梯的方法数（为了方便讨论，数组下标从 1 开始），dp[i] 表示走到第 i 个楼梯的方法数目。
第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。

考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2]，使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。

idea:

时间从指数级时间下降当线性级

class Solution {
  public int climbStairs(int n) {
      if( n <=2){
          return n;
      }
      int[] dp = new int[n+1];
      dp[1] = 1;
      dp[2] = 2;
      for(int i = 3; i<=n; i++){
          dp[i] = dp[i-1]+dp[i-2];
      }
      return dp[n];
  }
}

2 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i = 1; i <n+1; i++){
            dp[i] = i;
            for(int j = 1; i-j*j>=0; j++){
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}

3最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

思路

点不在边界情况时：有两条路径可以到达grid[i][j]， dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1])
在边界的时候，只有一条路径 dp[i][j] = grid[i][j] + dp[i][j + 1];
dp[i][j] = grid[i][j] + dp[i + 1][j];

public class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                if(i == grid.length - 1 && j != grid[0].length - 1)
                    dp[i][j] = grid[i][j] +  dp[i][j + 1];
                else if(j == grid[0].length - 1 && i != grid.length - 1)
                    dp[i][j] = grid[i][j] + dp[i + 1][j];
                else if(j != grid[0].length - 1 && i != grid.length - 1)
                    dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
                else
                    dp[i][j] = grid[i][j];
            }
        }
        return dp[0][0];
    }
}

4 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        int i , j;
        for(i = 0; i < m; i++){
            for(j = 0; j < n; j++){
                if(i==0 || j ==0){
                    f[i][j] = 1;
                }
                else{
                    f[i][j] = f[i][j-1] + f[i-1][j];
                }
            }
        }
        return f[m-1][n-1];
    }
}

5 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

给定一个数列，长度为N设> 动态规划 - 图25 为：以数列中第k项结尾的最长递增子序列的长度. 求> 动态规划 - 图26 中的最大值.

而对于来讲，都是的子问题：因为以第k项结尾的最长递增子序列（下称LIS），包含着以第中某项结尾的LIS。
上述的新问题也可以叫做状态，定义中的“为数列中第k项结尾的LIS的长度”，就叫做对状态的定义

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;

        //  第一步 计算下标i的最长上升子序列
        //  第二部 maxans， 对比每个下表为i的最长上升子序列的值保留最大值
        for (int i = 1; i < dp.length; i++) {
            int maxval = 0;
            // 前 1到i-1的最大长度对比， 找出最大长度。
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    maxval = Math.max(maxval, dp[j]);
                }
            }
            // 
            dp[i] = maxval + 1;
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }


}

6 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

class Solution {
    public int integerBreak(int n) {
        int[] res = new int[n+1];
        res[1] =1 ;
        res[2] = 1;
        for(int i = 3; i<=n; i++){
            for(int j = 1; j <=i-1 ; j++){


                res[i] = Math.max(res[i], Math.max(j * res[i-j], j*(i-j)));

            }
        }
        return res[n];
        }
}

背包问题

package com.company.ForTruth.ali.背包问题;

import java.util.Scanner;

/**
 * Author:   hszzjs
 * Date:     2019/5/10 13:41
 * E-mail:   hushaozhe@stu.xidian.edu.cn
 * 题目描述：完全背包
 * 有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 vi，价值是 wi。
 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
 输入格式
 第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
 输出格式
 输出一个整数，表示最大价值。
 数据范围
 0<N,V≤1000
 0<vi,wi≤1000
 输入样例
 4 5
 1 2
 2 4
 3 4
 4 5
 输出样例：
 10
 */
public class 完全背包 {
    /**
     * 完全背包问题，完全是基于01背包的扩展，问题就在于完全背包的物品件数是不限制的。所以相较于前面的，就是有一个个数k>=0，
     * 这样的做法时间复杂度是O(N*V)
     * 所以动态规划的递推公式就是：
     * dp(i,j)=Max{dp(i-1,j),dp(i,j-k*vi)+wi*k}其中k>=1
     *       =Max(dp(i-1,j),dp(i,j-vi-k*vi)+k*wi+wi),其中k>=0
     *       =Max(dp(i-1,j),dp(i+1,j-vi)+wi)
     * 参考链接：https://blog.csdn.net/zhao_xinhao/article/details/77153300
     * 然后完全背包问题是正序遍历。
     * 明显可以看到这个优化了的，未优化，就是对于k进行遍历，
     * 时间复杂度是O(N*V^2)
     */
    static class VW{
        int v,w;
        public VW(int v,int w){
            this.v=v;
            this.w=w;
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt(),V=sc.nextInt();
        VW[] vw=new VW[N];
        for(int i=0;i<N;i++){
            vw[i]=new VW(sc.nextInt(),sc.nextInt());
        }
        int[][] res=new int[N+1][V+1];
        //优化
//        for(int i=1;i<=N;i++){
//            for(int j=1;j<=V;j++){
//                if(vw[i-1].v>j) res[i][j]=res[i-1][j];
//                else res[i][j]=Math.max(res[i-1][j],res[i][j-vw[i-1].v]+vw[i-1].w);
//            }
//        }
        //未优化
        for(int i=1;i<=N;i++){
            for(int j=1;j<=V;j++){
                if(vw[i-1].v>j) res[i][j]=res[i-1][j];
                else {
                    for(int k=0;k*vw[i-1].v<=j;k++){
                        int tmp=res[i-1][j-k*vw[i-1].v]+k*vw[i-1].w;
                        if(tmp>res[i][j])
                            res[i][j]=tmp;
                    }
                }
            }
        }
        System.out.println(res[N][V]);
    }
}