动态规划（英语：Dynamic programming，简称 DP）
是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。斐波那契数列 0,1,1,2,3,5,8,13,…有着一个相当简单的描述方式，它的每个数字都与前两个紧邻的数字相关。如果 F(n) 是第 n 个数字，那么我们会有 F(n) = F(n-1) + F(n-2)。这个在数学上称作递归方程或者递推关系。为了计算后面的项，它需要前面项的计算结果作为输入。
解决方案
自上而下：
你从最顶端开始不断地分解问题，直到你看到问题已经分解到最小并已得到解决，之后只用返回保存的答案即可。这叫做记忆存储（Memoization）。
自下而上：
你可以直接开始解决较小的子问题，从而获得最好的解决方案。在此过程中，你需要保证在解决问题之前先解决子问题。这可以称为表格填充算法（Tabulation，table-filling algorithm**）。
至于迭代和递归与这两种方法的关系，自下而上用到了迭代技术，而自上而下则用到了递归技术。
动态规划、分治法、贪心算法异同点
相同点：
动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。
不同点：
-
分治法
分治法中的各个子问题是独立的，利用子问题的解，合并成该问题的解。
-
贪心算法
只有同一个问题，依赖于当前已经做出的所有选择。
自顶向下处理，每一步，根据策略得到一个当前最优解。传递到下一步，从而保证每一步都是选择当前最优的。
-
动态规划
动态规划中的各个子问题是不独立的，动态规划任何一个i+1阶段都仅仅依赖 i 阶段的处理，而与i之前的选择无关。
自底向上处理，每一步，根据策略得到一个更小规模的问题。最后解决最小规模的问题，得到整个问题最优解。
121. 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
题解：
class Solution {
public int maxProfit(int[] prices) {
//思路：从最后一天往前遍历，看最后一天卖出能得到的最大利润，依次往前得出每天卖出的最大利润，取出最大值为最大利润，如果最大值还为负数，则
//最大利润为0，不进行交易
int maxProfit = 0;
for (int i=prices.length-1;i>=1;i--) { //从第二天到最后一天都可能是卖出的天数，但第一天不能卖，因为还没买
for (int j=i-1;j>=0;j--) { //从卖出的前一天到第一天为可能买的日期，得出利润
if (prices[i]-prices[j] > maxProfit) {
//利润有更大的需要更新
maxProfit = prices[i]-prices[j];
}
}
}
return maxProfit;
}
}
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
题解1：
class Solution {
public int climbStairs(int n) {
//思路：用动态规划思想，要爬到n阶，可以通过最后爬一步和两步2中爬法到，到n阶的方法等于到n-1阶方法加上n-2阶方法，即f(n)=f(n-1)+f(n-2)，这个f(n)方法就用递归实现
//此外，f(n)=f(n-1)+f(n-2)，从n为3开始，该函数计算得出的是一个斐波那契数列，当前数为前两个数之和，所以有两种解法
if (n < 3) {
return n;
}
int a = 1;
int b = 2;
int cur = 0;
for (int i=3;i<=n;i++) {
cur = a + b;
a = b;
b = cur;
}
return cur;
}
}
题解2：
class Solution {
public int climbStairs(int n) {
//思路：用动态规划思想，要爬到n阶，可以通过最后爬一步和两步2中爬法到，到n阶的方法等于到n-1阶方法加上n-2阶方法，即f(n)=f(n-1)+f(n-2)，这个f(n)方法就用递归实现
return getStepWay(n);
}
/**
* 计算n级台阶不同走法
* @param n
* @return
*/
public int getStepWay(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return getStepWay(n-1) + getStepWay(n-2);
}
}
1025. 除数博弈
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。
示例 1：
输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。
示例 2：
输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
题解：
class Solution {
/**
* 思路：
* 动态规划，先从dp[1],dp[2]
* dp[n] 表示N=n时的结果，dp[n]类型为boolean类型 true为爱丽丝赢
* 那么dp[1]=false,dp[2]=true
* 然后往后推，如果i中有约数j，dp[i-j]=false，那么dp[i]=true
* 如果i中，所有dp[i-j]没有为false情况，那么dp[i]=false;
*
* 我们用DP来求解这个问题，首先new一个长度为N+1的数组，dp[i]表示i这个数是否可以赢，如果为true则N=i可以赢，为false则输。
* N=1，爱丽丝就肯定会输，所以我们首先让dp[1]=false;
* 然后我们从i=2开始，一直遍历到i=N
* 按照题意，我们让j每次从1到i-1的区间里取数，且需要满足
* 选出任一 x，满足 0 < x < N 且 N % x == 0 。
* 这个条件，如果发现dp[j]=false，那么dp[i]就一定会赢。
*/
public boolean divisorGame(int N) {
boolean[] dp = new boolean[N+1];
if (N == 1) {
return false;
}
dp[1] = false;
dp[2] = true;
for (int i=3;i<=N;i++) {
//i表示某次开始选择的数，用j表示下一次选的数，j为i的约数，所以j的范围为1到i/2
dp[i] = false;
for (int j=1;j<=i/2;j++) {
if (i%j==0 && dp[i-j]==false) {
//下一次人选的为false，那么该人就胜了，为ture
dp[i] = true;
break;
}
}
}
return dp[N];
}
/**
* 思路： 归纳法
* 如果数是奇数，因为只用1与本身才能让余数为0，所以必然会让接下来的数变为偶数
* 首先要明确的是，到谁是数为2，那么就是谁赢，所以如果刚开始数是偶数，那么每次就让爱丽丝选1，这样每次在奇数是就让鲍勃来选，再让数变为偶数，最后一定是到爱丽丝选时，数为2
* 同理，如果数为奇数，那么到鲍勃时数为偶数，鲍勃也这么做就能取得胜利，所以最后判断胜利条件，就是数的奇偶性
* @param N
* @return
*/
public boolean divisorGame(int N) {
return N%2==0;
}
}
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
题解：
class Solution {
/**
* 思路：
* 状态定义： 设动态规划列表dp ，dp[i]代表以元素nums[i]为结尾的连续子数组最大和。
*
* 我们发现dp[i]就是以数组下标为i的数做为结尾的最大子序列和，
* 注意是以i为结尾，比如说现在有一个数组{6,-3,-2,7,-15,1,2,2}，为了不搞，我们就下标以1开始，dp[3]就是以-2为结尾的，
* 那么显然dp[3]的最大值就是1咯（6，-3，-2），dp[4]要以7结尾那么以7结尾的子序列最大和就是8（6，-3，-2，7）。
*
* 知道dp[i]是啥后，现在我们开始细细品一下上面这个递推式，求dp[i]的时候是不是有两种可能，
* 要么就是像上面的dp[4]一样，dp[3]求出来是1了，再加上自己array[4]是最大的，那么还有一种可能就是说如果dp[3]我求出来是-100，
* 那如果我也是dp[3]+array[4]的话是-93，这时候dp[3]反而是累赘，最大就是自己（因为前面定义了必须以i为结尾，也就说必须以7结尾）。
*
* @param nums
* @return
*/
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for (int i=1;i<nums.length;i++) {
//如果i前一个数的子数组和小于0，就不要加上前面的累赘了，否则就加上
dp[i] = nums[i] + Math.max(dp[i-1], 0);
//遍历的同时获取dp数组中的最大值
if (dp[i] > max) {
max = dp[i];
}
}
return max;
}
}
网友评论