由于太久沒(méi)有復(fù)習(xí)算法知識(shí)尚蝌，導(dǎo)致基本沒(méi)寫(xiě)出來(lái)绅这，但是都是以前學(xué)過(guò)的知識(shí)车荔，編程題主要有兩道：
1.求矩陣最小路徑
給定一個(gè)矩陣m
從左上角開(kāi)始
每次只能往下或者往右走
最后到達(dá)右下角的位置
路徑上所有數(shù)字之和就是路徑和
求最小路徑和
用c++寫(xiě)的：
#include <iostream>
using namespace std;
int main() {
int m;
scanf("%d",&m);//輸入矩陣大小
int i,j,input[m][m],output[m][m];
for (i = 0 ; i<m; i++) {//輸入矩陣值
for (j = 0; j<m; j++) {
cin>>input[i][j];
output[i][j] = input[i][j];
}
}
for (i=1; i<m; i++) {
output[0][i] += output[0][i-1];//處理第一行
output[i][0] += output[i-1][0];//處理第一列
for (j=1; j<m; j++) {
output[i][j] += output[i][j-1]<output[i-1][j]?output[i][j-1]:output[i-1][j];//比較上方元素和左方元素值大小甘耿，取小
}
}
cout<<output[m-1][m-1]<<endl;//輸出答案
return 0;
}
2.求最少優(yōu)惠券使用數(shù)量
自行輸入用例：
商品價(jià)格搓茬，若干種面值的優(yōu)惠券（第一個(gè)數(shù)是種類(lèi)數(shù)量）
65
4 30 20 10 5
輸出使用優(yōu)惠券最少的最優(yōu)方案
（需要先排序）從大到小芽突，這里省略
function dikou(total, youhui) {
function _dikou(t, q, tmp) {
// console.log(tmp, q, q.length - 1)
if (t < q[q.length - 1] || tmp.length >= 5) return tmp
if (t - q[0] >= 0) {
tmp.push(q[0])
return _dikou(t - q[0], q, tmp)
} else {
return _dikou(t, q.slice(1), tmp)
}
}
let result = []
return _dikou(total, youhui, result)
}
console.log(dikou(65, [30, 20, 10, 5]))
