乐趣区

关于java:算法入门之动态规划

jiezi

动静布局

动静布局个别用于求最值问题，外围原理就是穷举，把所有答案算进去，求个最值不是轻轻松松吗？不过动静布局比穷举好的中央在于，动静布局存储了计算出来的值，再后续解决重叠子问题时，间接从内存获取。这就要求了动静布局解决的问题必须要有最优子结构，这样以后问题的值就能够通过子问题的最优解计算失去。

三要素

  1. 重叠子问题
  2. 最优子结构
  3. 状态转移方程

思路

  1. 间接创立一个数组存储子问题答案 dp[]
  2. 了解题意，写出状态转移方程 dp[i] 和 dp[i-1] 之间的关系
  3. 用代码写出状态转移方程即可

实际

题目一

leetcode338：比特位计数

思维过程

设 dp[] 为一个存储后果的数组汇合，当传入一个整数 i 时，能够失去二进制数 1 的个数为 dp[i]。
如何书写状态转移方程？dp[i] 和 dp[i-1] 之间存在什么关系？
带入二进制思考，整数 i 的二进数 1 的个数等于去除了二进制最高位的整数 x 的 1 的个数加 1。
举例：101 的 1 的个数等于 01 的 1 的个数 +1 -> dp[i] = dp[x] + 1 -> i = x + i 的最高位的值

代码 

 public static int[] countBits(int n) {int[] dp = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {if ((i & (i - 1)) == 0) {highBit = i;}
            dp[i] = dp[i - highBit] + 1;
        }
        return dp;
    }

代码解析

  1. 定义 dp 数组
  2. 定义 hightBit 为最高位的值，通过 i & (i – 1) 位运算计算
  3. 写 dp[i] = dp[i – highBit] + 1 状态转移方程

题目二

剑指 Offer 42：间断子数组的最大和

思维过程

设 dp[] 为一个存储后果的数组汇合，当传入一个整数 i 时，能够失去数组前 i 个值的最大和为 dp[i]。
如何书写状态转移方程？dp[i] 和 dp[i-1] 之间存在什么关系？
带入题目思考，题目要求是间断，所以 dp[i] 必然蕴含数组 nums[i] 的值，dp[i-1] 为正数时，对于 dp[i] 是个累赘，间接舍弃，如果 dp[i-1] 为负数，那么最大值为 dp[i-1] + nums[i]。
所以状态转移方程为：
当 dp[i-1]<0,dp[i] = nums[i]
当 dp[i-1]>=0,dp[i] = dp[i-1] + nums[i]

代码 

public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {if (i == 0) {max = nums[i];
                dp[i] = nums[i];
            } else {if (dp[i - 1] < 0) {dp[i] = nums[i];
                } else {dp[i] = dp[i - 1] + nums[i];
                }
                if (dp[i] > max) {max = dp[i];
                }
            }
        }
        return max;
    }

代码解析

  1. 定义 dp 数组
  2. 定义 max 保留最优解
  3. for 循环给 dp[0] 赋予初值之后，就是写出状态转移方程
退出移动版