动态规划算法OJ刷题(2)

CC88 不同路径的数目(一)

题目描述

一个机器人在m×n大小的地图的左上角（起点）。机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？

解题思路

• 状态F(i, j) : 从(0, 0)到(i, j)的路径个数
• 状态转移方程 : F(i-1, j) + F(i, j-1)
• 初始状态 : F(i, 0) = F(0, j) = 1
• 返回 : F(row-1, col-1)

class Solution {
public:/* * @param m int整型 * @param n int整型 * @return int整型*/int uniquePaths(int m, int n) {// write code herevector<vector<int>> ret(m, vector<int>(n, 1));//m-row，n-col//初始条件 第一行 = 第一列 = 1for(int i = 0; i < m; ++i)ret[i][0] = 1;for(int i = 0; i < n; ++i)ret[0][i] = 1;//状态转移方程for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){ret[i][j] = ret[i][j-1] + ret[i-1][j];}}return ret[m-1][n-1];}
};

CC86 带权值的最小路径和

题目描述

给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。注意：你每次只能向下或向右移动。

解题思路

• 状态F(i, j) : 从(0, 0)到(i, j)的最短路径和
• 状态转移方程 : min(F(i-1, j) + F(i, j-1)) + array[i][j]
• 初始状态 : F(0, 0) = array[0][0] F(i, 0) = F(i-1, 0) + array[i][0] F(0, j) = F(0, j-1) + array[0][j]
• 返回 : F(row-1, col-1)

class Solution {
public:/* * @param grid int整型vector<vector<>> * @return int整型*/int minPathSum(vector<vector<int> >& grid) {// write code herevector<vector<int>> ret(grid);int row = grid.size();int col = grid[0].size();//初始条件for(int i = 1; i < row; i++)ret[i][0] = ret[i-1][0] + grid[i][0];for(int i = 1; i < col; i++)ret[0][i] = ret[0][i-1] + grid[0][i];//转移方程for(int i = 1; i < row; ++i){for(int j = 1; j < col; ++j){ret[i][j] = min(ret[i-1][j], ret[i][j-1]) + grid[i][j];}}【return ret[row-1][col-1];}
};

背包问题（0，1背包）

问题描述

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值。问最多能装入背包的总价值是多大？

解题思路

状态范围索引是从1开始，价值数组和大小数组索引范围是从0开始，故第i个商品的容量为A[i-1]，价值为V[i-1]

这里就要用到二维数组来表示价值和容量的关系。

情况1：放入第i个商品但是要取出某个商品 F(i, j) = F(i-1, j - A[i-1]) + V[i]，j-A[i-1]表示容量要扣除掉第i个商品的体积【是第2种情况的子情况，因为对于背包的容量来说情况1和2都没超重】；

情况2：放入第i个商品 F(i, j) = F(i-1, j) + V[i]

情况3：不放入第i个商品，F(i, j) = F(i-1, j)【第i个商品放不下的时候，就会直接退化到上一个商品的状态值】

状态描述F(i, j) : 表示把第i个物品放入容量为j的背包中，此时该背包价值最大。

状态转移方程：如果A[i-1] > j ，表示情况3不放入第i个商品，F(i, j) = F(i-1, j)；如果A[i-1] <= j，表示情况1和2放入第i个商品，F(i, j) = max(F(i-1, j), F(i-1, j - A[i-1]) + V[i-1])；

初始值：F(0, j) = 0 表示包有足够的容量，但是没有放入任何商品，价值为0；F(i, 0) = 0表示包容量为0，故价值为0

返回 : F(n, m)

class Solution {
public:
/
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @param V: Given n items with value V[i]
* @return: The maximum value
*/
int backPackII(int m, vector<int> A, vector<int> V) {//若无商品或者无背包，则直接返回0if(A.empty() || V.empty() || m < 1)return 0;//多加一行一列，给初始条件赋值const int N = A.size() + 1;//物品个数const int M = m + 1;//背包数//初始条件 F(i, 0) = F(0, j) = 0vector<vector<int>> ret(N, vector<int>(M, 0));//状态递推for(int i = 1; i < N; ++i){for(int j = 1; j < M; ++j){//第i个商品在A中对应的索引为i-1: i从1开始//如果第i个商品大于j,说明放不下， 所以(i,j)的最大价值和(i-1,j)相同if(A[i-1] > j) ret[i][j] = ret[i-1][j];elseret[i][j] = max(ret[i-1][j], ret[i-1][j-A[i-1]] + V[i-1]);}}return ret[N-1][m];}
};//用一维数组实现，内内层循环要从后往前更新
const int N = A.size();//物品个数
const int M = m + 1;//背包数
vector<int> ret(M, 0);
for(int i = 1; i <= N; ++i)
{for(int j = M - 1; j > 0; --j){if(A[i] <= j) ret[j] = max(ret[j], ret[j-A[i]] + V[i]);else ret[j] = ret[j];}
}
return ret[m];