动态规划
什么是动态规划
按照定义，动态规划是把一个大问题拆解成一堆小问题，但是这个不是动态规划的核心思想。而取决于该问题是否能用动态规划解决的是这些"小问题“会不会被被重复调用。举一个例子“1+1+1+1=4”，如果在左侧在“+1”呢？你不会把右侧的4个“+1”重新算一遍，而是直接得出结论“1+4”。
题目特点
- 计数
- 有多少种方式走到右下角
- 有多少种方法选出k个数使得和是Sum
- 求最大最小值
- 从左上角到右下角路径的最大数字和
- 最长上升子序列长度
- 求存在性
- 取石头游戏，先手是否必胜
- 能不能选出k个数使得和是Sum
问题1
你有三种硬币，分别面值2元,5元和7元，每种硬币都有足够多，买一本书需要27元，如何用最少的硬币组合正好付清，不需要对方找钱。
我们不关心前面的K-1枚硬币是怎么拼出27-ak的(可能有1种拼法,可能 有100种拼法),而且我们现在甚至还不知道ax和K,但是我们确定前面的硬币拼出了27-ak。
如果ak是2,f(27)应该是f(27-2)+1(加上最后这一枚硬币2) ;
如果ak是5,(27)应该是f(27-5)+1(加上最后这一枚硬币5) ;
如果ak是7,f(27)应该是(27-7)+1(加上最后这一枚硬币7);
最后问题抽象为f[x]=min{f[x-2]+1,f[x-5]+1,f[x-7]+1}。
如果x-2，x-5，x-7小于0怎么办？我们规定这些拼不出来的都为最大值。所以有f[1]=min{f[-1]+1,f[-4]+1,f[-4]+1} = 最大值，它是拼不出来的。
最后附上代码：
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().coinChange(new int[]{2, 5, 7}, 27));
}
public int coinChange(int[] array, int m) {
int length = array.length;
// f[mounts] 代表mounts元下，使用的最少硬币数量
int[] f = new int[m + 1];
// 初始化
f[0] = 0;
for (int mounts = 1; mounts <= m; mounts++) {
f[mounts] = Integer.MAX_VALUE;
// 遍历硬币的种类
for (int j = 0; j < length; j++) {
// 如果mounts比
if (mounts >= array[j] && f[mounts - array[j]] != Integer.MAX_VALUE) {
f[mounts] = Math.min(f[mounts], f[mounts - array[j]] + 1);
}
}
}
if (f[m] == Integer.MAX_VALUE) return -1;
return f[m];
}
}
动态规划步骤
- 确定状态
- 转移方程
- 初始条件和边界情况
- 计算顺序
问题2
给定m行n列的网格,有一个机器人从左上角(00)出发,每一步可以向下
或者向右走一步，问有多少种不同的方式走到右下角。
我们按照前面的动态规划步骤来写思路。
- 确定状态
最后一步:无论机器人用何种方式到达右下角,总有最后挪动的一步向右或者向下，右下角坐标设为(m-1,n-1)，那么前一步机器人一定是在(m-2,n-1)或者(m-1,n-2)。状态:设f[i][j]为机器人有多少种方式从左上角走到(i,j)。 - 转移方程
f[i][j] = f[i-1][j] + f[i][j-1] - 初始条件和边界情况
初始条件：f[0][0] = 1
边界情况：i=0或j=0，则前一步只能有一个方向过来，即f[0][j] = 1, f[i][0] = 1 -
计算顺序
因为我们每次都要得到左边和上边一个格子的值，所以先遍历行，后遍历列。
由此这个问题就分析完了，下面是完整代码：
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().uniquePaths(4, 8));
}
public int uniquePaths(int m, int n) {
int[][] f = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
f[i][j] = 1;
continue;
}
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
}
问题3
有n块石头分别在x轴的0,1,...,n-1的位置一只青蛙在石头0,想跳到石头n-1。如果青蛙在第i块石头上,它最多可以向右跳距离ai，问青蛙能否跳到石头n-1。
例子：
输入:a=[2,3,1,1,4] 输出:True
输入:a=[3,2,1,0,4] 输出:False
-
确定状态
最后一步:如果青蛙能跳到最后一块石头n-1,我们考虑它跳的最后一步。这一步是从石头i跳过来,i<n-1。这需要两个条件同时满足1.青蛙可以跳到石头；2.最后一步不超过跳跃的最大距离:n-1-i<=a。设f[i]表示青蛙能不能跳到石头i。 -
转移方程
f[i] = OR(f[j] && a[j] + j >= i)
-
初始条件和边界情况
f[0] = True -
计算顺序
按顺序分别计算 f[1],...,f[n-1]
以下是完整代码：
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().canJump(new int[]{3, 2, 1, 0, 4}));
}
public boolean canJump(int[] a) {
boolean[] f = new boolean[a.length];
f[0] = true;
for (int i = 1; i < a.length; i++) {
f[i] = false;
for (int j = 0; j < i; j++) {
if (f[j] && a[j] + j >= i) {
f[i] = true;
break;
}
}
}
return f[a.length - 1];
}
}
问题4
最大乘积子序列：给定a[0],...,a[n-1],找到最长的连续子序列i,i+1,i+2,i+j,使得a[i] * ... * a[j]最大
例子：
输入:[2,3,-2,4]
输出:6(子序列[2,3]:2*3=6)
-
确定状态
有最大子序列的最后一个元素a[j]，第一种情况，最大为a[j]本身;第二种情况，如果a[j]大于0，我们希望a[j-1]结尾的最大子序列最大，如果a[j]小于0，则反之。
所以问题的关键是我们需要同时保留最大值和最小值。状态:f[i]=以a[j]结尾的连续子序列的最大乘积,设g[j]=以a[j]结尾的连续子序列的最小乘积。 -
转移方程
这里有个小技巧，我们其实可以不管是否大于0的问题。
f[j] = Math.max(a[j], Math.max(a[j] * f[j-1], a[j] * g(j-1)))
g[j] = Math.min(a[j], Math.min(a[j] * f[j-1], a[j] * g(j-1))) -
初始条件和边界情况
无 -
计算顺序
f[0], g[0], f[1], g[1], f[2], g[2],..., f[n-1], g[n-1]
以下是完整代码：
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().maxSubArray(new int[]{2, 3, -2, 4}));
}
public int maxSubArray(int[] a) {
int[] f = new int[a.length];
int[] g = new int[a.length];
int result = Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
f[i] = a[i];
if (i > 0) {
f[i] = Math.max(a[i], Math.max(f[i - 1] * a[i], g[i - 1] * a[i]));
}
if (f[i] > result) {
result = f[i];
}
g[i] = a[i];
if (i > 0) {
g[i] = Math.min(a[i], Math.min(f[i - 1] * a[i], g[i - 1] * a[i]));
}
}
return result;
}
}
问题5
有n个阶梯，一个人每一步只能跨一个台阶或是两个台阶，问这个人一共有多少种走法？
-
确定状态
f[n]是到第n级台阶有几种走法 -
转移方程
到第n级台阶只有两种可能，从第n-1上来，从n-2上来。
f[n] = f[n-1] + f[n-2] -
初始条件和边界情况
f[0] = 1
f[1] = 1 -
计算顺序
无
以下是完整代码
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().climbStairs(3));
}
public int climbStairs(int n) {
int[] f = new int[n + 1];
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
}
问题6
给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
示例1:
输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
示例2:
输入: n = 10
输出：4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
有以下的思路
/*
f(k, n) = f(k-1, n) 前 k-1 个硬币组成 n - COIN * 0 分的情况（第 k 个硬币使用 0 个）
+ f(k-1, n-COIN) 前 k-1 个硬币组成 n - COIN * 1 分的情况（第 k 个硬币使用 1 个）
+ f(k-1, n-COIN*2) 前 k-1 个硬币组成 n - COIN * 2 分的情况（第 k 个硬币使用 2 个）
+ ... ...
+ f(k-1, n-COIN*i) 前 k-1 个硬币组成 n - COIN * i 分的情况（第 k 个硬币使用 i 个）
当 n - COIN*i < 0 时循环停止。
*/
以下代码就是上述思路的体现，但是在leecode中会超时
class Solution {
static int[] coins = new int[]{0, 1, 5, 10, 25};
// 前k个硬币组成n分有几种情况？
public static int f(int k, int n) {
if (k == 1) {
return 1;
}
int currentCoin = coins[k];
int result = 0;
for (int i = 0; n - currentCoin * i >= 0; i++) {
result += f(k - 1, n - currentCoin * i);
}
return result;
}
public int waysToChange(int n) {
return f(4, n);
}
}
