第一题：上台阶问题
题目：有一个楼梯总共n个台阶，只能往上走，每次只能上1个、2个台阶，总共有多少种走法。
分析：最后一步有两种走法，一种是上一阶（n-1->n）,另一种是上两阶（n-2->n）；
用dp[n]来 表示n个台阶的走法，那么就有：dp[n]=dp[n-1]+dp[n-2]；
代码：
//上台阶问题（count为台阶总数）
int step(int count){
if(count == 1){
return (1);
}
if(count == 2){
return (2);
}
else{
return step(count -1) + step(count - 2);
}
}
第二题：数塔问题
题目：有如图所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
数塔问题.jpeg
分析：
1.要到达第i层，先要到达第i-1层。并且第i层的第j个节点，只能由i-1层的第j个和第j-1个节点到达；用dp[i][j]来表示到达第i层，第j个的时候最大的情况，那么有dp[i][j]=max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];
2.第1层的第1个节点，初始值为dp[1][1]=a[1][1]。（a[x][y]表示第x层，第y个的值）；
3.要考虑到上层只有一个节点到达下层的情况，只有左边或者只有右边；
代码：
//数塔问题（求到达第i层第j个元素时数字之和的最大值）
//求整个数塔最大元素只需要将第n层（n为数塔层数）的元素遍历一下，取最大值即可
int tower(int i, int j){
//初始数据
NSArray *orgin = @[@[@"9"],@[@"12",@"15"],@[@"10",@"6",@"8"],@[@"2",@"18",@"9",@"5"],@[@"19",@"7",@"10",@"4",@"16"]];
//当到达第一层的时候
if(i == 0){
return [orgin[0][0] intValue];
}else{
if(j > 0){
if(j > i){
//当上层右侧没有数据
return tower(i-1, j-1) + [orgin[i][j-1] intValue];
}
return MAX(tower(i-1, j), tower(i-1, j-1)) + [orgin[i][j] intValue];
}else{
//当上层左侧没有数据
return tower(i-1, j) + [orgin[i][j] intValue];
}
}
}
第三题：背包问题
题目：给定n件物品和一个容量为m的背包，每件物品都会消耗背包的一定容积c[i]，并带来一定价值v[i]，要求如何选取装入背包中的物品，使得背包内的物品价值最大。
i(编号) 1 2 3 4
w(体积) 2 3 4 5
v(价值) 3 4 5 6
分析：要装第i个物品，就要分为两种情况，能不能装的下。装不下就免谈了，就是装了i-1件物品，如果可以装的下的话，又分为两种情况，要不要装（用f[i][j]来表示i件物品，j容量下的最大值）。
1.装不下：f[i][j] = f[i-1][j]；
2.装的下&&要装：f[i][j] = f[i-1][j-c[i]]+v[i];（重点理解这个）
3.装的下&&不要装：f[i][j] = f[i-1][j]；
综上所述：f[i][j] = max(f[i-1][j], f[i-1][j-c[i]]+v[i])；
代码：
//背包问题（i代表物品个数，j代表背包容量）
int bagMatrix(int i,int j){
//为了可以编号从1开始，将物品和价值前面添加一个0
NSArray *weght = @[@(0),@(2),@(3),@(4),@(5)];
NSArray *value = @[@(0),@(3),@(4),@(5),@(6)];
//没有物品或者没有容量背包的价值为0
if(i==0 ||j== 0){
return 0;
}
//背包放不下第i个物品
if(j < [weght[i] intValue]){
return bagMatrix(i-1, j);
}else{
//背包不放第i个物品的价值
int x = bagMatrix(i-1, j);
//背包放第i个物品的价值
int y = bagMatrix(i-1, j-[weght[i] intValue]) + [value[i] intValue];
return x < y ? y : x;
}
}
本文参考CocoaChina上面的文章：程序员算法基础——动态规划。
网友评论