๋ฌธ์ ๋งํฌ
m*n ํ๋ ฌ์ด ์ฃผ์ด์ง๋ ๋ก๋ด์ [0][0]์์ ์ถ๋ฐํด์ [m-1][n-1]๋ก ๋์ฐฉํ๋ คํ๋ค.
์ด๋ ๋ก๋ด์ด ๋์ฐฉ์ง์ ๊ฐ ์ ์๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ์ฌ๋ผ
์กฐ๊ฑด : ๋ก๋ด์ ์ค๋ฅธ์ชฝ๊ณผ ์๋๋ก๋ง ์ด๋ํ ์ ์๋ค.
์ ๊ทผ ๋ฐฉ๋ฒ
1. Dynamic Programming ๋ฐฉ๋ฒ์ผ๋ก ํ์ด
2. ์ฌ๊ทํจ์ ๋ฐฉ์์ผ๋ก ํ์ด
1. DP๋ก ํ์ด๋ฅผ ํ๊ธฐ ์ํด์๋ ๊ท์น์ ๋ฐ๊ฒฌํด์ผํ๋ค.๊ท์น์ ๊ทธ๋ฆผ์ผ๋ก ๋ณด๋ฉด ๋ ์ฌ์ด๋ฐ
์ด์ ํ๊ณผ ์ด์ ์ด์ ๊ฐ์ ๋ํ๋ฉด ๋ค์ ํ์ด์ ๊ฐ์ด ๋์จ๋ค.
์ฆ, dp[row][col] = dp[row-1][col] + dp[row][col-1]
2์ฐจ ํ๋ ฌ์ ๋ค๋ฃจ๋ฏ๋ก 2์ค for๋ฌธ์ด ํ์ํ๋ค.
const dp = Array.from({length : m}, () => Array(n).fill(1)); for(let row = 1; row < m; row++){ for(let col = 1; col < n; col++){ dp[row][col] = dp[row-1][col] + dp[row][col-1]; } }โ
dp[0][0] ~ dp[m][0] === 1
dp[0][0] ~ dp[0][n] === 1
์ด๋ฏ๋ก 2์ฐจ์ ๋ฐฐ์ด์ ์์ฑํ ๋ 1๋ก ์ฑ์์ค๋ค.
๊ทธ๋ฆฌ๊ณ 2์ค for๋ฌธ์ ํตํด ๊ท์น์ ๋ง์ถฐ ๊ฐ์ ๋ฃ์ด์ค๋ค.
2. ์ฌ๊ทํจ์
์ฌ๊ทํจ์ ์ญ์ ๊ท์น๊ณผ ์ข ๋ฃ ์กฐ๊ฑด์ ์ฐพ์์ผํ๋ค.
์ข ๋ฃ ์กฐ๊ฑด์ ์๋์ ๊ฐ์ด ๊ตฌํ๋ค.if(row > m || col > n){ return 0; }else if(row === m && col === n){ return 1; }
row์ col์ด ๋ฒ์๋ฅผ ๋ฒ์ด๋๋ฉด 0์ผ๋ก ์ข ๋ฃํ๊ณ , ๋ชฉ์ ์ง์ ๋์ฐฉํ๋ฉด 1์ ๋ฐํํ๋ค.
๋ฐ๋ณต์ ์๋์ ๊ฐ์ด ํ๋์ ๋ชฉ์ ์ง๋ก ๊ฐ๋ฅ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ ๋๊น์ง ๋ฐ๋ณตํ๋ค.return re(row+1, col) + re(row, col+1);
ํ์ง๋ง ์ฌ๊ทํจ์๋ก๋ m = 23, n = 12 ์ฒ๋ผ ํฐ ๋ฒ์๋ฅผ ๊ตฌํ์ง ๋ชปํ๋ค.
๊ฐ๋ฐ์ ๋๊ตฌ์์๋ ์๊ฐ ์ ํ์ด ์๊ธฐ๋๋ฌธ์ dp์ ๊ฐ์ ๊ฐ์ ๊ตฌํ ์ ์์์ง๋ง leetcode์์๋ ์คํจํ์๋ค.
// DP ๋ฐฉ๋ฒ
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
const dp = Array.from({length : m}, () => Array(n).fill(1));
for(let row = 1; row < m; row++){
for(let col = 1; col < n; col++){
dp[row][col] = dp[row-1][col] + dp[row][col-1];
}
}
return dp[m-1][n-1];
}
// ์ฌ๊ท ๋ฐฉ๋ฒ
var uniquePaths = function(m, n) {
const re = (row, col) => {
if(row > m || col > n){
return 0;
}else if(row === m && col === n){
return 1;
}
return re(row+1, col) + re(row, col+1);
}
return re(1, 1)
};
'์ฝ๋ฉํ ์คํธ > LeetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[LeetCode] My Calendar I (0) | 2022.08.03 |
---|---|
[LeetCode] Kth Smallest Element In A Sorted Matrix (0) | 2022.08.02 |
[LeetCode] Find And Replace Pattern (0) | 2022.07.29 |
[LeetCode] Valid Anagram (0) | 2022.07.28 |
[LeetCode] Median Of Two Sorted Arrays (0) | 2022.07.25 |