首页 > 试题广场 > 请指出以下代码段使用了何种算法public voi
[单选题]
请指出以下代码段使用了何种算法
public void func(int[] arr1, int k, int m,int[] arr2) {
arr2[0] = 0;
for (int i = 1; i <= m; i++) {
int min = i;
for (int j = 0; j < k; j++) {
if (arr1[j] <= i) {
int temp = arr2[i - arr1[j]] + 1;
if (temp < min) {
min = temp;
}
}
}
arr2[i] = min;
}
}
  • 分治算法
  • 动态规划
  • 贪心算法
  • 回溯算法
b
1.分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
排序算法(快速排序归并排序)都属于分治法
2.动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。即适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的。
3.贪心算法是指:在每一步求解的步骤中,它要求“贪婪”的选择最佳操作,并希望通过一系列的最优选择,能够产生一个问题的(全局的)最优解。简单来说:若活动越早结束,剩余的时间是不是越多?那我就早最早结束的那个活动,找到后在剩下的活动中再找最早结束的不就得了
4.回溯算法实际上一个类似枚举的深度优先搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回(也就是递归返回),尝试别的路径。
发表于 2019-04-26 20:19:51 回复(0)