剑指Offer刷题笔记：动态规划

动态规划

斐波那契解法

斐波那契数列

递归

public int Fibonacci(int n) {
    // 时间复杂度：O(2^n)，空间复杂度：O(n)
	if(n <= 2)
        return 1;
    return Fibonacci(n-1) + Fibonacci(n-2);
}

改进递归：数组保存重复计算值

public int Fibonacci(int n) {
    // 时间复杂度：O(n)，无重复计算
    // 空间复杂度：O(n)，数组和递归栈
    int[] res = new int[50];//数组长度取决于题目要求，本题1<=n<=40
    if(n <= 2)
        return 1;
    if(res[n] > 0)
        return res[n];
    res[n] = Fibonacci(n-1) + Fibonacci(n-2);
    return res[n];
}

动态规划

public int Fibonacci(int n) {
    // 时间复杂度：O(n)，无重复计算
    // 空间复杂度：O(n)，数组
    int[] dp = new int[50];
    dp[1] = 1;
    dp[2] = 1;
    for(int i = 3; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

优化动态规划

public int Fibonacci(int n) {
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)，只用到了最近的两个值
    int one = 1;
    int two = 1;
    int sum = 0;
    for(int i = 3; i <= n; i++){
        sum = one + two;
        one = two;
        two = sum;
    }
    return sum;
}

矩形覆盖

思路

F(1) = 1, F(2) = 2, F(3) = F(1) + F(2)

F(4) = F(2) + F(3), F(5) = F(3) + F(4)

即 F(n) = F(n-2) + F(n-1)

所以等同于斐波那契数列

代码

public int rectCover(int target) {
    if(target <= 2)
        return target;
    int one = 1;
    int two = 2;
    int sum = 0;
    for(int i = 3; i<=target; i++){
        sum = one + two;
        one = two;
        two = sum;
    }
    return sum;
}

跳台阶

思路

由下至上为跳台阶 -> 由上至下下台阶：

如果从第n个台阶向下，下一步有两种可能，n-1级台阶或n-2级台阶

那么到达第n级台阶的跳法，就是到达第n-1级与n-2级之和

则有：F(n) = F(n-1) + F(n-2)，跳到n级台阶的跳法 = n-1 + n-2 级跳法

即转化为斐波那契数列

初始值：F(0) = 1, F(1) = 1

代码

public int jumpFloor(int target) {
    // 优化动态规划：只保存最近的两个值
    if(target <= 1)
        return 1;
    int one = 1;
    int two = 1;
    int sum = 0;
    for(int i = 2; i<=target; i++){
        sum = one + two;
        one = two;
        two = sum;
    }
    return sum;
}

变态跳台阶

暴力遍历：超时

public int jumpFloorII(int target) {
    // 暴力遍历
    if(target <= 1)
        return 1;
    int[] res = new int[target+1];
    res[0] = 1;
    res[1] = 1;
    for(int i = 2; i<=target; i++)
        for(int j = 0; j<i; j++)
            res[i] += res[j];
    return res[target];
}

递推

public int jumpFloorII(int target) {
    // F(n) = F(n-1) + F(n-2) +...+ F(0)    #1
    // F(n-1) = F(n-2) + F(n-3) +...+ F(0)  #2
    // #1 - #2 = F(n) - F(n-1) = F(n-1)
    // 即 F(n) = 2*F(n-1)
    if(target <= 1)
        return 1;
    int one = 1, two = 1;
    for(int i = 2; i<=target; i++){
        two = one << 1;
        one = two;
    }
    return two;
}

优化递推

public int jumpFloorII(int target) {
    // F(0) = F(1) = 1 = 2^0
    // F(2) = 2 = 2^1
    // F(3) = 4 = 2^2
    // F(4) = 8 = 2^3
    if(target <= 1)
        return 1;
    return 1 <<(target-1);
}

状态转移

连续子数组的最大和（求最大值）

暴力遍历：超时

public int FindGreatestSumOfSubArray(int[] array) {
    // 时间复杂度：O(n^2)，空间复杂度O(1)
    int max = array[0];
    int sum = 0;
    for(int i = 0; i < array.length; i++){
        sum = 0;
        for(int j = i; j < array.length; j++){
            sum += array[j];
            max = Math.max(max,sum);
        }
    }
    return max;
}

动态规划

public int FindGreatestSumOfSubArray(int[] array) {
    // 时间复杂度：O(n)，空间复杂度O(n)
    // 创建动态规划结果列表dp，dp[i]表示以array[i]为结尾的连续子数组最大和
    // 状态转移方程：dp[i] = Math.max(dp[i-1]+array[i],array[i])
    // 思路：
    //    1. 遍历数组，判断array当前值加上dp上一个结果是否会变小
    //    2. 为保证子数组的和最大，每次比较sum取较大值
    //    3. 用max记录计算过程中的连续最大和dp[i]
    int[] dp = new int[array.length];
    dp[0] = array[0];

    int max = dp[0];
    for(int i = 1; i < array.length; i++){
        // 动态规划：状态转移方程，确定dp[i]最大值
        dp[i] = Math.max(dp[i-1]+array[i],array[i]);
        // 每次比较，保存出现的最大值
        max = Math.max(max,dp[i]);
    }
    return max;
}

优化动态规划

public int FindGreatestSumOfSubArray(int[] array) {
    // 优化动态规划
    // 时间复杂度：O(n)，空间复杂度O(1)，只保存最大值与数组当前值
    int max = array[0];
    int sum = 0;
    for(int i = 0; i < array.length; i++){
        sum = Math.max(array[i]+sum,array[i]);
        max = Math.max(max,sum);
    }
    return max;
}

连续子数组的最大和（求最大值的子数组）

public int[] FindGreatestSumOfSubArray (int[] array) {
    // write code here
    // dp[i]记录当前数组之和结果
    // 设置left,right双指针，标记当前数组起始位置
    // 设置snapLeft,snapRight双指针，标记最大和数组中最长的起始位置
    // 移动left,right遍历数组，数组和存入dp[i]
    // 遇到最大和时，判断数组长度，snap指针保存较长数组，保存数组长度，保存最大和
    // 遍历结果数组，从array中取值填充
    int[] dp = new int[array.length];
    dp[0] = array[0];

    int left = 0, right = 0;
    int snapLeft = 0, snapRight = 0;
    int maxSum = array[0], maxLength = 1;

    for(int i = 1; i < array.length; i++){
        right++;
        dp[i] = Math.max(dp[i-1]+array[i],array[i]);
        if(dp[i-1]+array[i] < array[i])
            left = right;
        if(dp[i] > maxSum || 
           dp[i] == maxSum && (right-left+1) > maxLength){
            snapLeft = left;
            snapRight = right;
            maxLength = right-left+1;
            maxSum = dp[i];
        }
    }
    int[] res = new int[maxLength];
    int idx = 0;
    for(int i = snapLeft; i < snapRight+1; i++ )
        res[idx++] = array[i];
    return res;
}

礼物最大价值（二维数组最大路径）

public int maxValue (int[][] grid) {
    // write code here
    // 动态规划：
    // dp[x][y]记录到达(x,y)位置时的礼物最大价值
    // 每次遍历所有列，得到一行的dp，遍历次数为行数
    // 状态转移方程：
    // dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1],[j]) + grid[i][j]
    // 即：当前位置礼物最大价值 = 上一格和左一格的较大值 + 当前位置礼物价值
    // 时间复杂度：O(n*m)，空间复杂度：O(n*m)

    int[][] dp = new int[201][201];
    dp[1][1] = grid[0][0];
    for(int i = 0; i<grid.length; i++){
        for(int j = 0; j<grid[0].length; j++){
            dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j]) + grid[i][j];
        }
    }
    return dp[grid.length][grid[0].length];
}

最长不含重复字符的子字符串

public int lengthOfLongestSubstring (String s) {
    // write code here
    // 动态规划：
    // dp[i]存放以i结尾的不含重复字符的子字符串长度
    // array[]存放字符串中每个字符
    // Map<>存放字符与位置的映射关系
    // 遍历array[]，判断当前字符是否重复
    //    若不重复，则dp[i]=dp[i-1]+1，当前子字符串长度+1
    //    若重复，则dp[i]=i-map.get(array[i])，当前位置-前一个位置
    //        但此时可能出现：
    //        字符串abba，dp[0]=1 dp[1]=2 dp[2]=1 dp[3]=3
    //        显然dp[3]错误，因为bb重复
    //        所以应改为：dp[i]=Math.min(dp[i-1]+1,i-map.get(array[i]))
    //    每次遍历，在Map记录当前字符和位置，更新maxLength

    // 特殊情况：
    if(s == null)
        return 0;
    if(s.length() == 1)
        return 1;
    char[] array = s.toCharArray();
    int[] dp = new int[array.length];
    Map<Character,Integer> map = new HashMap<>();

    dp[0] = 1;
    map.put(array[0],0);
    int maxLength = 1;
    for(int i = 1; i<array.length; i++){
        if(!map.containsKey(array[i])){
            dp[i] = dp[i-1] + 1;
        }else{
            dp[i] = Math.min(dp[i-1]+1,i-map.get(array[i]));
        }
        map.put(array[i],i);
        maxLength = Math.max(dp[i],maxLength);
    }
    return maxLength;
}

把数字翻译成字符串

public int solve (String nums) {
    // write code here
    // 动态规划：
    //    F(n) = F(n-1) + F(n-2)
    // 考虑条件：
    //    1.判断第i位是否为0，决定结果数组是否需要加上F(n-1)
    //      若不为0则需要加，dp[i]=dp[i-1]
    //      若为0则不需要加
    //    2.判断第i-1位和第i位的组合数字是否大于10且小于26
    //      若符合条件，则dp[i]+=dp[i-2]
    //                特殊值，i==1，即初始值F(1)，直接dp[i]++

    // 特殊情况：
    if(nums.length() == 0 || nums.charAt(0) == '0')
        return 0;
    int[] dp = new int[nums.length()];
    dp[0] = 1;
    for(int i = 1; i<nums.length(); i++){
        if(nums.charAt(i) != '0')
            dp[i] = dp[i-1];
        int num = (nums.charAt(i-1)-'0')*10 + (nums.charAt(i)-'0');
        if(num >= 10 && num <= 26){
            if(i == 1)
                dp[i] += 1;
            else
                dp[i] += dp[i-2];
        }
    }
    return dp[nums.length()-1];
}