我要评论题目特点
1.计数
- 有多少种方式走到右下角
- 有多少种方法选出k个数使得和为sum
2.求最值
- 从左上角走到右下角路径的最大数字和
- 最长上升子序列长度
3.求存在性
- 取石子游戏，先手是否必胜
- 能不能选出k个数使得和为sum
题目特点
组成部分一：确定状态
简单来说，解动态规划的时候需要开一个数组，数组的每个元素f[i]或f[i][j]代表什么（类似于解数学题中，X、Y、Z 代表什么）
确定状态需要两个意识：
最后一步（最优策略中的最后一个决策）
子问题（问题相同，但规模变小）
组成部分二：转移方程
组成部分三：初始条件和边界情况
其中初始条件往往是用转移方程无法求得出结果，需要人为定义。
组成部分四：计算顺序
大多数情况：从小到大（一维）从上到下从左到右（二维）
例题
例题一（LintCode 669:Coin Change）（求最值型）
你有三种硬币，分别面值2元，5元和7元，每种硬币都有足够多
买一本书需要27元
如何用最少的硬币组合正好付清，不需要对方找钱
分析
1.确定状态
此时最后一枚硬币为最后一步（即去掉这一步后，前面的K-1枚硬币依然为最优策略）
所以此时问题可以从原来的“最少用多少枚硬币拼出27”转化为一个子问题，而且规模更小“最少用多少枚硬币可以拼出27-ak”。
为简化定义，设状态f(x) = 最少用多少枚硬币拼出x
由于ak的取值情况只可能是2,5或者7
故如果ak为2，则f(27) = f(27-2) + 1(加上最后这一枚硬币2)
如果ak为2，则f(27) = f(27-5) + 1(加上最后这一枚硬币5)
如果ak为2，则f(27) = f(27-7) + 1(加上最后这一枚硬币7)
需要求最少的硬币数，所以：
f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}
2.转移方程
转移方程形式：f[x] = min{f[27-2]+1, f[27-5]+1, f[27-7]+1}
3.初始条件和边界情况
若不能拼出Y，则定义f[Y] = +∞
eg：f[1] = min{f[-1]+1, f[-4]+1, f[-6]+1} = +∞ （表示拼不出来1）
初始条件：f[0] = 0
4.计算顺序
计算f[1],f[2],f[3],…,f[27]
当我们计算到f[x]时，f[x-2],f[x-5],f[x-7]都已经得到结果了
代码部分
class Solution {
public:
/**
* @param coins: a list of integer
* @param amount: a total amount of money amount
* @return: the fewest number of coins that you need to make up
*/
const int MAX_VALUE = 0x3f3f3f3f; //无穷大
int coinChange(vector<int> &coins, int amount) {
// write your code here
int result[amount + 1]; //+1表示我这里需要用到 amount
result[0] = 0; //初始条件
for (int i = 1; i <= amount; i++)
{
result[i] = MAX_VALUE; //先初始化为最大值，这里是考虑到了不存在硬币的情况
for (int j = 0; j < coins.size(); j++)
{
if (i >= coins[j] && result[i - coins[j]] != MAX_VALUE)
{
result[i] = min(result[i - coins[j]] + 1, result[i]); //就是那条公式的一个转换
}
}
}
if (result[amount] == MAX_VALUE)
return -1;
else
return result[amount];
}
};
例题二（LintCode 114:Unique Paths）（计数型）
给定m行n列的网格，有一个机器人从左上角（0,0）出发，每一步可以向下或者向右走一步
问有多少种不同的方式走到右下角
分析
1.确定状态
最后一步：无论机器人用何种方式到达右下角，总有最后挪动一步：向右或向下
右下角坐标设为（m-1，n-1）
则前一步机器人一定在（m-2，n-1）或（m-1，n-2）
子问题：
原题“求有多少种方式从左上角走到（m-1，n-1）”
子问题“求有多少种方式从左上角走到（m-2，n-1）和（m-1，n-2）”
状态：设f[i][j]为机器人有多少种方式从左上角走到（i，j）（有多少变量就开几维数组）
2.转移方程
对于任意一个格子（i，j）
f[i][j]：有多少种方式从左上角走到（i，j）
f[i][j] = f[i-1][j] + f[i][j-1]
3.初始条件和边界情况
初始条件：f[0][0] = 1 //机器人只有一种方式到左上角
边界情况：i=0或j=0，则前一步只能由一个方向过来—>f[i][j] = 1
4.计算顺序
f[0][0] = 1
计算第0行：f[0][0]，f[0][1]，f[0][2]，…，f[0][n-1]
计算第1行：f[1][0]，f[1][1]，f[1][2]，…，f[1][n-1]
…
计算第m-1行：f[m-1][0]，f[m-1][1]，f[m-1][2]，…，f[m-1][n-1]
答案：f[m-1][n-1]
时间复杂度度（计算步数）：O（mn）
空间复杂度（数组大小）：O（mn）
代码部分
class Solution {
public:
/**
* @param m: positive integer (1 <= m <= 100)
* @param n: positive integer (1 <= n <= 100)
* @return: An integer
*/
int uniquePaths(int m, int n) {
// write your code here
int f[m][n];
for(int i=0;i<m;i++){ // row : top to bottom
for(int j=0;j<n;j++){ // column: left to right
if(i == 0 || j == 0)
f[i][j] = 1;
else
f[i][j] = f[i-1][j] + f[i][j-1];
}
}
return f[m-1][n-1];
}
};
例题三（LintCode 116:Jump Game）（存在性型）
有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
1.确定状态
最后一步：如果青蛙能跳到最后一块石头n-1，我们考虑它跳的最后一步
这一步是从石头i跳过来，i < n-1
这需要两个条件同时满足：
a.青蛙可以跳到石头i
b.最后一步不超过最大跳跃距离：n-1-i <= ai
子问题：
原问题“求青蛙能不能跳到石头n-1”
子问题“求青蛙能不能跳到石头i(i < n-1)”
状态：设f[j]表示青蛙能不能跳到石头j
2.转移方程
设f[j]表示青蛙能不能跳到石头j
f[j] = OR(0<= i <=j-1)(f[i] AND i + a[i] >= j)
其中
(0<= i <=j-1)表示枚举上一个跳到石头i
f[i]表示青蛙能不能跳到石头i
i + a[i] >= j 表示最后一步不能超过ai
OR表示只要有一个i满足即返回true，否则返回false
3.初始条件和边界情况
初始条件：f[0] = True，因为青蛙一开始就在石头0
边界情况：不会越界
4.计算顺序
计算f[0], f[1], f[2], … , f[n-1]
答案是f[n-1]
时间复杂度：O（N^2） 空间复杂度（数组大学）：O（N）
代码部分
class Solution {
public:
/**
* @param A: A list of integers
* @return: A boolean
*/
bool canJump(vector<int> &A) {
// write your code here
int n = A.size();
bool f[n];
f[0] = true; // initialization
for(int j=1;j<n;j++){
f[j] = false;
// previous stone i
// last jump is from i to j
for(int i=0;i<j;i++){
if(f[i] && i + A[i] >= j){
f[j] = true;
break;
}
}
}
return f[n-1];
}
};
总结
确定状态
研究最优策略的最后一步
化为子问题
转移方程
根据子问题定义直接得到
初始条件和边界情况
细心、考虑周全
计算顺序
利用之前的结果
本文地址：https://blog.csdn.net/qq_43662165/article/details/108566880
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论