动态规划题目特点
1.计数的问题
有多少种方式走到右下角
有多少种方法选出k个数使得和是Sum
2.求最大值最小值
从左上角走到右下角路径的最大数字和
最长上升子序列长度
3.求存在性
取石子游戏，先手是否必胜
能不能选出k个数使得和是Sum
以上是动态规划能够解题的题目种类。
1. 例题1：
假设有三种硬币，分别面值2元，5元，7元，每种硬币都足够的多，需要买一本27元的书，要求硬币数量尽可能的少
动态规划组成部分1：确定状态
动态规划一般需要一个额外的空间记录状态，一般是开一个数组
题目的最优策略是什么？该题目最优策略是K枚硬币A1…Ak的面值加起来是27，索引一定有一枚最后的硬币Ak，除去该硬币前面的k-1硬币之和为27-Ak
关键点1：对于前面的K-1枚硬币是如何组成的不需要关系，而且也不知道Ak和K，但是知道了前面的硬币得到的是27-Ak
关键点2：因为最优策略，所以拼出27-Ak的硬币数量一定要少，否则就不是最优策略
原问题：最少用多少枚硬币拼出27
子问题：最少用多少枚硬币拼出27-Ak
f(x) = 使用多少枚硬币拼出x+1
根据最后一枚硬币的可能性，最后一枚是2,5,7
如果Ak为2,f(27)=f(27-2)+1加上最后一枚硬币
如果Ak为5,f(27)=f(27-5)+1加上最后一枚硬币
如果Ak为7,f(27)=f(27-7)+1加上最后一枚硬币
最后取三种结果的最小值，f(27) = min(f(27)=f(27-2)+1,f(27)=f(27-5)+1,f(27)=f(27-7)+1)
采用递归实现
int coin(int x){
if(x==0)return 0;
int res = Integer.MAX_VALUE;
if(x>=2)res = Math.min(res,coin(x-2)+1);
if(x>=5)res = Math.min(res,coin(x-5)+1);
if(x>=7)res = Math.min(res,coin(x-7)+1);
return res;
}递归运算的缺点是：计算的中间结果比较多，会产生重复的计算过程。
动态规划组成部分2：转移方程
对于任意x,状态转移方程 f[x] = min {f[x-2]+1,f[x-5]+1,f[x-7]+1}
动态规划组成部分3：初始条件和边界情况
f[x] = min {f[x-2]+1,f[x-5]+1,f[x-7]+1}
对于中间状态可能会产生小于0的状态，即边界控制条件。如果拼不出y值，则返回系统最大值，f[y]=系统最大，不会影响其他的判断。例如，f[1] = min{f[-1]+1,f[-4]+1,f[-6]+1}，2,5,7拼不出来1
初始条件是f[0] = 0
动态规划组成部分4：计算顺序
一般来书都是从前向后，从上向下计算，当然也存在例外。
时间复杂度：n*m,n表示需要拼出的数值，m表示硬币面值数，本题目时间复杂度是27*3
题目小结：
动态规划组成部分：
1.确定状态
最后一步(最优策略中使用的最后一枚硬币)
化成子问题
2.转移方程
f[x] = min{f[x-2]+1,f[x-5]+1,f[x-7]+1}
3.初始条件和边界情况
f[0] = 0,如果不能拼出Y，f[Y] = 正无穷
4.计算顺序
f[0],f[1]…
// 钱数最小
public static int coin(int val, int[] coins) {
// 初始化一个数组，记录中间状态
int[] dp = new int[val + 1];
// 原始位置初始化
dp[0] = 0;
for (int i = 1; i <= val; i++) {
dp[i] = Integer.MAX_VALUE;
for (int j = 0; j < coins.length; j++) {
if (i >= coins[j] && dp[i - coins[j]] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
}
}
}
if (dp[val] == Integer.MAX_VALUE) {
dp[val] = -1;
}
return dp[val];
}2.例题2
计数型的动态规划
给定一个m行n列的网格，有一个机器人从左上角(0,0出发，每一步可以向下或者向右走一步)，问题是有多少种不同的方式走到右下角。
原问题：从(0,0)位置到达(m-1,n-1)位置
子问题：最后一个位置能到达是由于机器人要么来自其上方，要么来自其左方。即来自(m-1,n-2)或者(m-2,n-1)
初始条件和边界
初始条件：f[0][0] = 1
边界条件：i=0;j=0,只有一个方向到达
计算顺序
计算第0行：f[0][0],f[0][1]…f[0][n-1]
计算第1行：f[1][0],f[1][1]…f[1][n-1]
….
计算第m-1行：f[m-1][0],f[m-1][1]…f[m-1][n-1]
最终的结果是f[m-1][n-1]
时间复杂度O(MN),空间复杂度O(MN)
// 获取路径
public static int getPath(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}3.例题3
青蛙跳台阶，在n块石头分别在x轴的0,1…n-1的位置，一只青蛙在石头0，想要跳到石头n-1，如果青蛙在第i块石头上，他最多可以向右跳距离ai，问青蛙是否可以跳到石头n-1。
输入:a=[2,3,1,1,4]
输出:true
确定状态：
假设青蛙能够跳到最后一块石头n-1，其前一步是在第i块石头上跳过来的，i<n-1，这两个条件同时满足，青蛙可以跳到石头i，最后一步不超过跳跃的最大距离：n-1-i<=ai
子问题：确定青蛙能不能跳到i位置的石头
转移方程：f[i] = Skip(f[i] AND i+a[i]>=j)，f[i]表示青蛙能不能跳到i位置
初始条件：f[0] = true，因为青蛙一开始就在石头0
计算顺序：f[0] f[2]…f[n-1]
时间复杂度O(N^2),空间复杂度O(N)
public static boolean skip(int[] num) {
boolean[] skip = new boolean[num.length];
skip[0] = true;
for (int i = 1; i < skip.length; ++i) {
skip[i] = false;
for (int j = 0; j < i; ++j) {
if (skip[j] && j + num[j] >= i) {
skip[j] = true;
break;
}
}
}
return skip[num.length - 1];
}
