动态规划三个经典问题(Object-C)

第一题：上台阶问题

题目：有一个楼梯总共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上面的文章：程序员算法基础——动态规划。