欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CVTE 2018 Android在线笔试编程题

程序员文章站 2024-01-23 11:11:46
...

CVTE 2018 Android在线笔试编程题

暴力求解(错误思路)
1.遍历第i行找出该行最小值
2.记录当前行最小值列角标t;
3.遍历i+1行最小值时,跳过第t列;

/**
public static int minPrice(int [][]p){
        int res=0;
        int t=0;
        int index = 0;
        for (int i = 0; i < p.length; i++) {
            int min=0x70000000;//设定一个最大值
            for (int j = 0; j < p[0].length; j++) {
                if(j!=t&&min>p[i][j]){
                    min=p[i][j];
                    index=j;
                }
            }
            t=index;
            res+=min;       
        }
        return res;
    }
    **/
  • 动态规划
    设dp[i][j]表示第i个人选择第j件衣服时当前总费用。
    第1个人可选衣服时总费用:dp[0][j]=p[0][j]={1,2,3,4};
    第2个人可选衣服时总费用:dp[1][j]={3,3,4,5};
    第3个人可选衣服时总费用:dp[2][j]={4,5,6,7};
    第4个人可选衣服时总费用:dp[3][j]={6,6,7,8};

测试:输入p[][]={{1,2,3,4},{1,2,3,4},{1,2,3,4},{1,2,3,4}};
输出res=6;

相关标签: CVTE