1.有数组penny,penny中所有的值都为正数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim(小于等于1000)代表要找的钱数,求换钱有多少种方法。
给定数组penny及它的大小(小于等于50),同时给定一个整数aim,请返回有多少种方法可以凑成aim。
测试样例:
[1,2,4],3,3
返回:2
penny[i]代表货币的面值。
f[n],n代表可以组成的面值。f[n]代表可以组成的方法。 f[0] 代表组成0,只有一种方法,就是不选任何货币,就可以组成0;
f[j] 代表组成j,有几种方法,等于使用n-1个penny[i]的值的方法。循环累加到aim,最后就得到了组成aim的方法。 例如:
penny[i]=5,那么组成的数,是f[5],f[10],f[15] ,能被5整除的,都为前一个加上当前的值。
当所有面值的货币,都循环完成,就得到了所求值。
class Exchange {
public:
int countWays(vector<int> penny, int n, int aim) {
int f[];
memset(f,,sizeof(f)); f[] = ;
for(int i = ;i < n;++ i)
for(int j = penny[i];j <= aim;++ j)
f[j] += f[j - penny[i]];
return f[aim];
}
};
2.有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。为了防止溢出,请将结果Mod 1000000007
给定一个正整数int n,请返回一个数,代表上楼的方式数。保证n小于等于100000。
#define Mod 1000000007
class GoUpstairs {
public:
int cnt[];
int countWays(int n) {
cnt[] = ;
for(int i = ;i <= n;++ i)
cnt[i] = ((i >= ? cnt[i - ] : ) + (i >= ? cnt[i - ] : )) % Mod;
return cnt[n];
}
};
这个题可以是使用2个变量,循环交替的增加就可以了。就会占用连续内存了。
3.有一个矩阵map,它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有的路径中最小的路径和。
给定一个矩阵map及它的行数n和列数m,请返回最小路径和。保证行列数均小于等于100.
测试样例:
[[1,2,3],[1,1,1]],2,3
返回:4
class MinimumPath {
public:
int getMin(vector<vector<int> > map, int n, int m) {
// write code here
vector<vector<int> > dp(n,vector<int>(m)); dp[][] = map[][]; for(int i=;i<n;i++){
dp[i][] = map[i][] + dp[i-][];
}
for(int i=;i<m;i++){
dp[][i] = map[][i] + dp[][i-];
}
for(int i=;i<n;i++){
for(int j=;j<m;j++){
dp[i][j] = min(dp[i][j-]+map[i][j],dp[i-][j]+map[i][j]);
}
}
return dp[n-][m-];
}
};
4.这是一个经典的LIS(即最长上升子序列)问题,请设计一个尽量优的解法求出序列的最长上升子序列的长度。
给定一个序列A及它的长度n(长度小于等于500),请返回LIS的长度。
测试样例:
[1,4,2,5,3],5
返回:3
int getNum(vector<int>a){ vector<int>dp(a.size()); if (a.size() < )return ;
if (a.size() == )return a[]; int len = a.size();
dp[] = ;
for (int i = ; i < len; i++){
for (int j = ; j < i; j++){
if (a[i]>a[j]){
dp[i] = max(dp[i], dp[j] + );
}
}
}
return dp[len - ];
}