第一句话。动态规划对于不会的人来说真的，难，爆，了！
第二句话。动态规划对于会的人来说，其实更多的只是一个转移方程。
而面试中我们遇到的动态规划题，其实很有套路，面试官并不会为了某个人特意去造题。并且，一道太难的题，很浪费面试时间。而给你coding的时间其实只有15分钟而已。
也就是说，出于各种原因，面试中，常见的动态规划们，基本都是，常见的，简单的，因此我们只需要了解基础算法就可以了。作为一个菜鸡，就介绍菜鸡至少要会的程度就行了，再难的我也不会啊，毕竟。
首先，怎么样判断一道题是不是动态规划呢？
主要有三种情况：
（1）求多少种情况
（2）求最优解
（3）博弈
但是对于动态规划来说，其实做题只需要考虑四个步骤：
（1）确定状态
--最后一步
--子问题拆分
（2）转移方程
（3）边界和初始条件
（4）计算顺序
每种情况都举个例子吧
（1）有多少种情况——典型例题
零钱兑换
零钱兑换题目
首先找最后一步，对于例子来说，硬币【1,2,5】求满足目标为11的最少组合。
那么最后一步肯定是这样的。
f[11]
= Min{f[11-1]+1,f[11-2]+1,f[11-5]+1}
= Min{f[10]+1,f[9]+1,f[6]+1}
有三种情况，组成目标11的最后一块硬币是1，或者2，或者5。
然后再向前查找，组成目标为10 / 9 / 6的最少硬币个数，直到目标为f[0]，即初始状态。
所以我们的状态转移方程如下：
f[amount] = Min{f[amount-coins[i]+1,f[amount]]}
所以代码如下：
class Solution {
public int coinChange(int[] coins, int amount) {
//确定状态
//转移方程
//边界和初始条件
//计算顺序
//定义组成0-amount的结果集
Arrays.sort(coins);
int[] f = new int[amount+1];
//硬币集
int len = coins.length;
//定义初始状态
f[0] = 0;
//填充结果集，最终的f[amount]就是最终解
for(int j = 1;j<amount+1;j++){
//因为要求最小组合，所以，初始化设置为最大int值
f[j] = Integer.MAX_VALUE;
//遍历硬币群，找到最优解
for(int i = 0;i<len;i++){
//最后一步，如果要找到和为amount的最少硬币组合，那么上一步是找到和为amount-coins[i]的最少硬币集
if(j>=coins[i]&&f[j-coins[i]]!=Integer.MAX_VALUE){
f[j] = Math.min(f[j-coins[i]]+1,f[j]);
}
}
}
if(f[amount]==Integer.MAX_VALUE){
f[amount]=-1;
}
return f[amount];
}
}
（2）求最优解
leetcode有一组问题，买卖股票的最佳时机，都是这个问题的典型例子。
买卖股票的最佳时机
买卖股票的最佳时机2
买卖股票的最佳时机3
买卖股票的最佳时机4
买卖股票的最佳时机
看题目，最大利润是多少？求最优解，可以考虑动态规划，那么首先，
老套路，看最后一步的状态。
用示例1来看，[7,1,5,3,6,4]的最大利润就是当第6天的时候的最大利润是多少。
那么第六天的最大利润是多少呢？
因为只能进行一笔交易，所以，要么是之前就卖过了，所以现在的最大利润就是之前的最大利润；要么就是当天卖出的，也就是之前持有股票今天卖了。
我们把是否持有股票当做一个状态，0表示没有持有，1表示持有。所以：
f[6][0] (最后一天，不持有股票，已经完成交易)= Max{f[5][0]（昨天或之前已经不持有股票了（卖过了））,f[5][1]（昨天持有股票）+prices6};
状态转移方程为：
f[n][0] = max{f[n-1][0],f[n-1][1]+prices[n]}
f[n][1] = max{f[n-1][1],0-prices[ｎ]}
当持有股票的时候，也就是购入的时候，可能是昨天就已经持有，也可能是当天购买，购入是支出，所以当天的利润为负值。
状态转移方程中主要需要两个状态，所以我们设置一下初始状态。
初始状态为：
f[0][0] = 0;(第0天，没有持有股票)
f[0][1] = -prices[0]（第0天，买入股票）
所以，代码为：
class Solution {
public int maxProfit(int[] prices) {
//确定状态
//转移方程
//边界，初始化
//计算顺序
//拿到需要的结果集状态数组
int n = prices.length;
if(n<1){
return 0;
}
//定义结果集
int[][] f = new int[n][2];
//初始状态
f[0][0] = 0;
f[0][1] = -prices[0];
for(int i = 1;i<n;i++){
f[i][0] = Math.max(f[i-1][0],f[i-1][1]+prices[i]);
f[i][1] = Math.max(f[i-1][1], -prices[i]);
}
return f[n-1][0];
}
}
买卖股票的最佳时机2
这道题和上道题的区别在于可以多次买入卖出。
但是对于我们来说，
最后一步依然是
f[6][0] (最后一天，不持有股票，已经完成交易)= Max{f[5][0]（昨天或之前已经不持有股票了（卖过了））,f[5][1]（昨天持有股票）+prices6};
那么区别是什么，区别在于，每次持有股票的时候，他可能是前一天已经买入股票;也可能是前一天刚好卖掉股票，今天购入。所以：
状态转移方程为：
f[n][0] = max{f[n-1][0],f[n-1][1]+prices[n]}
f[n][1] = max{f[n-1][1],f[n-1][0]-prices[n]}
那么代码写起来也很简单：
class Solution {
public int maxProfit(int[] prices) {
//确定状态
//转移方程
//初始，边界
//计算顺序
int n = prices.length;
if(n<1){
return 0;
}
int[][] f = new int[n][2];
//0持有现金
//1持有股票
f[0][0] = 0;
f[0][1] = -prices[0];
for(int i = 1;i<n;i++){
f[i][0]=Math.max(f[i-1][0],f[i-1][1]+prices[i]);
f[i][1]=Math.max(f[i-1][1],f[i-1][0]-prices[i]);
}
return f[n-1][0];
}
}
买卖股票的最佳时机3
这道题与上一道题的区别是什么，在于限制了交易次数，只能够交易两次。
所以我们需要一个新的变量k表示交易次数（第几次买入，卖出）。
首先，还是判断最后一步：
对于最后一天（第八天）（k<=2），
f[8][0][k]（对于第八天，如果已经完成了第k次交易，且不持有股票） = max{f[7][0][k]（有可能是第七天就已经完成了第k次交易的，且不持有股票）,f[7][1][k]+prices[8]（或者是第七天开始进行第k次交易，且持有股票，在第八天卖出，完成第k次交易）}
f[8][1][k]（对于第八天，如果开始了第k次交易（未完成），且持有股票） = max{f[7][1][k]（有可能是第七天就已经开始了第k次交易（未完成），且持有股票），f[7][0][k-1]-prices[8]（或者是，第七天完成了第k-1次交易，并在第八天开始第k次交易，购入股票）}
因此状态转移方程为：
f[i][1][k] = Math.max(f[i-1][1][k],f[i-1][0][k-1]-prices[i]);
f[i][0][k] = Math.max(f[i-1][0][k],f[i-1][1][k]+prices[i]);
初始状态为：
f[0][1][k] = -prices[0];
f[0][0][k] = 0;
所以代码如下：
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if(n<2){
return 0;
}
//记录的次数，是否持有股票的状态
//结果集，是否持有股票，进行第几次交易
int[][][] f = new int[n][2][3];
for(int i = 0;i<3;i++){
f[0][1][i] = -prices[0];
}
for(int i = 1;i<n;i++){
for(int k = 1;k<=2;k++){
//第k次买入
f[i][1][k] = Math.max(f[i-1][1][k],f[i-1][0][k-1]-prices[i]);
//第k次卖出
f[i][0][k] = Math.max(f[i-1][0][k],f[i-1][1][k]+prices[i]);
}
}
return f[n-1][0][2];
}
}
最后一题不再赘述，只是把k=2变成一个k=あるInteger。
所以只需要更改循环中k的大小值就可以。
至于博弈的题目前还没做到，但是思路都是一致的哦，可以试试看这个步骤！
終わり！
网友评论