CVTE 2018 Android在线笔试编程题
程序员文章站
2024-01-23 11:11:46
...
暴力求解(错误思路)
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;
下一篇: 简单的存储过程的使用