[이코테] -DP

기존에 있는 정보를 추합해서 새로운 정보를 뽑아내는 알고리즘

<2> 1로 만들기

const proj_1 = function (find) {

 var hey = Array.from({ length: find + 1 }, () => 100);
 hey[1] = 1;
 hey[2] = 1;
 hey[5] = 1;
 hey[3] = 1;

 for (var i = 2; i <= find; i++) {

  hey[i] = Math.min( hey[i - 1] + 1,hey[i]);
  if (i % 5 == 0) {
   hey[i] = Math.min(hey[i / 5] + 1, hey[i]);

  }
  if (i % 3 == 0) {
   hey[i] = Math.min(hey[i / 3] + 1, hey[i]);

  }
  if (i % 2 == 0) {
   console.log('뭐임?', hey[i / 2] + 1, hey[i],i);

   hey[i] = Math.min(hey[i / 2] + 1, hey[i]);
  }



 }
 console.log(hey[find], hey)

}
proj_1(26)

여기서 책이랑 다른 부분은
hey[1] = 1;
hey[2] = 1;
hey[5] = 1;
hey[3] = 1;
선언과
hey[i] = Math.min( hey[i - 1] + 1,hey[i]);
이 부분인데 .. 책이 오류인지 내가 오류인지..
어쨋든 답은 3

<3>개미전사

1. 원래의 array 나누고
2. dp array 새로 만들어서 비교하는 식

const pro_2 = function (arr) {
 
 var ma_arr = Array.from({ length: arr.length}, () => 100);

 ma_arr[0] = arr[0];
 ma_arr[1] = arr[1];
 var max = Math.max(ma_arr[0], ma_arr[1]);


 for (var i = 2; i < arr.length; i++){
  ma_arr[i] = Math.max(ma_arr[i-1], ma_arr[i-2] + arr[i]);
 
 }
 console.log(ma_arr)
}

pro_2([1,3,1,5])

그림에서

<4> 바닥공사

d[i]= d[i-1] + d[i-2] *2 ;

<5> 효율적인 화폐 구성

const pro_3 = function (a,final) {
 
 var check_arr = Array.from({ length: final+1 }, () => 100);
 check_arr[0] = 0;

 for (var i = 0; i < a.length; i++)
 {
  for (var z = a[i]; z <= final; z++){
   if (check_arr[z - a[i]] != 100) {
    console.log(check_arr[z], check_arr[z - a[i]] + 1, z,i)
    check_arr[z] = Math.min(check_arr[z], check_arr[z - a[i]] + 1); 
    }

  }
  console.log(check_arr)
  }
 console.log(check_arr)


}
pro_3([2,3,5],7)

0을기준으로 2 3 5 을 한번식 돌아간다. 이때 나를 사용하면서 ( 2,3,5) 중 하나
기존의 값을 활용할수 있나 없나를 확인하는 식이다.
예를들면 내가 3 을 활용하면서
5를 알고 싶을때
a[5] 의 값과 a[5-3]+1 여기서
+1 < 나를 사용하겠다는 의미이고
a[5-3] 은 기존 배열에 저장되어 있는 값을 사용하겠다 는 의미이다.

for문을 돌다보니 오류가 발생하였다.
이때 나를 기준으로 for 문을 돌아야된다.
var z = a[i]; < 으로 돌아봅시다.