215 lines
8.8 KiB
HTML
215 lines
8.8 KiB
HTML
|
<!DOCTYPE html>
|
|||
|
|
<html lang="zh-Hans">
|
|||
|
|
<head>
|
|||
|
|
<meta charset="UTF-8">
|
|||
|
|
<meta name="viewport" content="width=device-width, initial-scale=1.0">
|
|||
|
|
<title>091. 不同路径 – 图解</title>
|
|||
|
|
<link rel="stylesheet" href="../shared/style.css">
|
|||
|
|
<style>.vis-area { min-height: 120px; padding: 16px 0; } .code-section { margin-top: 16px; }
|
|||
|
|
.grid-vis{display:inline-grid;gap:3px;margin:8px auto;}
|
|||
|
|
.grid-cell2{min-width:48px;min-height:48px;display:flex;flex-direction:column;align-items:center;justify-content:center;font-family:var(--mono);border-radius:4px;background:var(--surface2);border:2px solid var(--border);transition:all .25s;padding:2px;}
|
|||
|
|
.grid-cell2 .gval{font-size:.9rem;font-weight:700;}
|
|||
|
|
.grid-cell2.computing{border-color:var(--orange);background:var(--orange-dim);}
|
|||
|
|
.grid-cell2.filled{border-color:var(--accent);background:rgba(108,126,255,.08);}
|
|||
|
|
.grid-cell2.origin{border-color:var(--purple);background:var(--purple-dim);}
|
|||
|
|
.grid-cell2.dest{border-color:var(--green);background:var(--green-dim);}
|
|||
|
|
.arrrow-row{display:flex;gap:2px;justify-content:center;margin-top:6px;font-size:.7rem;color:var(--text2);font-family:var(--mono);}
|
|||
|
|
</style>
|
|||
|
|
</head>
|
|||
|
|
<body><div class="container">
|
|||
|
|
<h1>🟡 091. 不同路径 <span class="badge medium">中等</span></h1>
|
|||
|
|
<p class="subtitle">分类：动态规划 ｜ LeetCode Hot 100</p>
|
|||
|
|
<div class="controls" id="controls">
|
|||
|
|
<label>m×n：</label><input type="text" id="inputArea" value="3,7">
|
|||
|
|
<button id="applyBtn" class="primary">生成图解</button>
|
|||
|
|
<select id="exampleSelect"></select>
|
|||
|
|
<span style="flex:1"></span>
|
|||
|
|
<button id="prevBtn">◀ 上一步</button>
|
|||
|
|
<button id="nextBtn">下一步 ▶</button>
|
|||
|
|
<button id="jumpBtn">⏭ 跳到结果</button>
|
|||
|
|
<button id="autoBtn">自动播放</button>
|
|||
|
|
<button id="resetBtn">重置</button>
|
|||
|
|
</div>
|
|||
|
|
<div class="pipeline" id="pipeline"></div>
|
|||
|
|
<div class="hint info" id="hintBox"><span id="stepInfo"></span><br><span id="hintText"></span></div>
|
|||
|
|
<div class="panels">
|
|||
|
|
<div class="panel" id="mainPanel"><h3>📊 可视化</h3><div class="vis-area" id="vizArea"></div></div>
|
|||
|
|
<div class="panel-grid">
|
|||
|
|
<div class="panel" id="detailPanel"><h3>📝 当前步骤详情</h3><div id="detailContent"></div></div>
|
|||
|
|
<div class="panel" id="resultPanel"><h3>✅ 结果</h3><div id="resultContent"></div></div>
|
|||
|
|
</div>
|
|||
|
|
</div>
|
|||
|
|
<div class="panel code-section"><h3>💻 参考代码（Python）</h3><div id="codeArea"></div></div>
|
|||
|
|
<footer>Powered by QwenPaw · 图解算法 · LeetCode Hot 100</footer>
|
|||
|
|
</div>
|
|||
|
|
<script src="../shared/algo-viz.js"></script>
|
|||
|
|
<script>"use strict";(function(){
|
|||
|
|
const CODE = `def uniquePaths(m, n):
|
|||
|
|
dp = [[1]*n for _ in range(m)]
|
|||
|
|
for i in range(1, m):
|
|||
|
|
for j in range(1, n):
|
|||
|
|
dp[i][j] = dp[i-1][j] + dp[i][j-1]
|
|||
|
|
return dp[m-1][n-1]`;
|
|||
|
|
|
|||
|
|
const EXAMPLES = [
|
|||
|
|
{ name: '例1: 3×7', input: '3,7' },
|
|||
|
|
{ name: '例2: 3×2', input: '3,2' },
|
|||
|
|
{ name: '例3: 7×3', input: '7,3' },
|
|||
|
|
{ name: '例4: 1×1', input: '1,1' },
|
|||
|
|
{ name: '例5: 4×4', input: '4,4' },
|
|||
|
|
];
|
|||
|
|
|
|||
|
|
let controller = null;
|
|||
|
|
|
|||
|
|
function genSteps(m, n) {
|
|||
|
|
const steps = [];
|
|||
|
|
const dp = Array.from({length: m}, () => Array(n).fill(null));
|
|||
|
|
|
|||
|
|
steps.push({
|
|||
|
|
desc: '初始化：第一行和第一列均为 1（只有一种走法）',
|
|||
|
|
hint: '机器人只能向右或向下走，第一行/列只有一条路径到达。',
|
|||
|
|
detail: '<b>思路</b>：dp[i][j] = 从 (0,0) 到 (i,j) 的不同路径数<br>• dp[i][j] = dp[i-1][j] + dp[i][j-1]<br>• 第一行 dp[0][j] = 1<br>• 第一列 dp[i][0] = 1<br><br>时间 O(mn)，空间 O(mn)',
|
|||
|
|
hlLine: -1, curI: -1, curJ: -1,
|
|||
|
|
dp: dp.map(r => [...r]),
|
|||
|
|
});
|
|||
|
|
|
|||
|
|
// fill first row & col with 1
|
|||
|
|
for (let j = 0; j < n; j++) dp[0][j] = 1;
|
|||
|
|
for (let i = 0; i < m; i++) dp[i][0] = 1;
|
|||
|
|
|
|||
|
|
steps.push({
|
|||
|
|
desc: '第一行/列初始化为 1',
|
|||
|
|
hint: '边缘格子只有一种到达方式。',
|
|||
|
|
detail: `dp[0][j] = 1（j=0..${n-1}）<br>dp[i][0] = 1（i=0..${m-1}）`,
|
|||
|
|
hlLine: 2, curI: -1, curJ: -1,
|
|||
|
|
dp: dp.map(r => [...r]),
|
|||
|
|
});
|
|||
|
|
|
|||
|
|
// fill rest
|
|||
|
|
for (let i = 1; i < m; i++) {
|
|||
|
|
for (let j = 1; j < n; j++) {
|
|||
|
|
dp[i][j] = dp[i-1][j] + dp[i][j-1];
|
|||
|
|
steps.push({
|
|||
|
|
desc: `dp[${i}][${j}] = dp[${i-1}][${j}] + dp[${i}][${j-1}] = ${dp[i-1][j]} + ${dp[i][j-1]} = ${dp[i][j]}`,
|
|||
|
|
hint: `从上方 (${dp[i-1][j]} 条路) 和左方 (${dp[i][j-1]} 条路) 汇聚。`,
|
|||
|
|
detail: `dp[${i}][${j}] = dp[${i-1}][${j}] + dp[${i}][${j-1}]<br>= <span style="color:var(--blue)">↑${dp[i-1][j]}</span> + <span style="color:var(--orange)">←${dp[i][j-1]}</span><br>= <b>${dp[i][j]}</b> 条路径`,
|
|||
|
|
hlLine: 4, curI: i, curJ: j,
|
|||
|
|
dp: dp.map(r => [...r]),
|
|||
|
|
});
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
steps.push({
|
|||
|
|
desc: `计算完成，不同路径数 = ${dp[m-1][n-1]}`,
|
|||
|
|
hint: 'dp 表已全部填充，右下角即为答案。',
|
|||
|
|
detail: `<b>结果</b>：从 (0,0) 到 (${m-1},${n-1}) 共有 <b>${dp[m-1][n-1]}</b> 条不同路径`,
|
|||
|
|
hlLine: 5, curI: -1, curJ: -1,
|
|||
|
|
dp: dp.map(r => [...r]), result: dp[m-1][n-1], isFinal: true,
|
|||
|
|
});
|
|||
|
|
|
|||
|
|
return steps;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function renderStep(step) {
|
|||
|
|
if (!step) {
|
|||
|
|
$('vizArea').innerHTML = '<div style="color:var(--text2);text-align:center;padding:40px;">点击「生成图解」开始</div>';
|
|||
|
|
$('detailContent').innerHTML = $('resultContent').innerHTML = '';
|
|||
|
|
$('stepInfo').textContent = $('hintText').textContent = '';
|
|||
|
|
return;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
$('stepInfo').textContent = step.desc;
|
|||
|
|
$('hintText').textContent = step.hint;
|
|||
|
|
$('detailContent').innerHTML = step.detail;
|
|||
|
|
|
|||
|
|
const { m, n } = parseMN($('inputArea').value);
|
|||
|
|
const dp = step.dp;
|
|||
|
|
|
|||
|
|
const g = document.createElement('div');
|
|||
|
|
g.className = 'grid-vis';
|
|||
|
|
g.style.gridTemplateColumns = `repeat(${n}, auto)`;
|
|||
|
|
|
|||
|
|
for (let i = 0; i < m; i++) {
|
|||
|
|
for (let j = 0; j < n; j++) {
|
|||
|
|
const cell = document.createElement('div');
|
|||
|
|
let cls = 'grid-cell2';
|
|||
|
|
if (i === step.curI && j === step.curJ) cls += ' computing';
|
|||
|
|
else if (dp[i] && dp[i][j] !== null) cls += ' filled';
|
|||
|
|
if (i === 0 && j === 0) cls += ' origin';
|
|||
|
|
if (i === m - 1 && j === n - 1 && dp[m-1] && dp[m-1][n-1] !== null) cls += ' dest';
|
|||
|
|
cell.className = cls;
|
|||
|
|
cell.innerHTML = `<span class="gval">${dp[i] && dp[i][j] !== null ? dp[i][j] : ''}</span>`;
|
|||
|
|
g.appendChild(cell);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
$('vizArea').innerHTML = '';
|
|||
|
|
const wrapper = document.createElement('div');
|
|||
|
|
wrapper.style.cssText = 'display:flex;justify-content:center;';
|
|||
|
|
wrapper.appendChild(g);
|
|||
|
|
$('vizArea').appendChild(wrapper);
|
|||
|
|
|
|||
|
|
// arrow row to show direction
|
|||
|
|
if (step.curI > 0 || step.curJ > 0) {
|
|||
|
|
const arrowRow = document.createElement('div');
|
|||
|
|
arrowRow.className = 'arrrow-row';
|
|||
|
|
arrowRow.innerHTML = '↑ 从上方贡献 ← 从左方贡献';
|
|||
|
|
$('vizArea').appendChild(arrowRow);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
const legend = document.createElement('div');
|
|||
|
|
legend.className = 'legend';
|
|||
|
|
legend.innerHTML = `
|
|||
|
|
<span class="legend-item"><span class="legend-dot" style="background:var(--purple)"></span> 起点</span>
|
|||
|
|
<span class="legend-item"><span class="legend-dot" style="background:var(--orange)"></span> 正在计算</span>
|
|||
|
|
<span class="legend-item"><span class="legend-dot" style="background:var(--accent)"></span> 已填充</span>
|
|||
|
|
<span class="legend-item"><span class="legend-dot" style="background:var(--green)"></span> 终点</span>
|
|||
|
|
`;
|
|||
|
|
$('vizArea').appendChild(legend);
|
|||
|
|
|
|||
|
|
renderCode($('codeArea'), CODE, step.hlLine);
|
|||
|
|
|
|||
|
|
if (step.isFinal) {
|
|||
|
|
$('resultContent').innerHTML = `<div class="result-box">不同路径数 = <span class="val">${step.result}</span></div>`;
|
|||
|
|
} else {
|
|||
|
|
$('resultContent').innerHTML = `<div style="color:var(--text2);font-size:.85rem;">等待填充完成…</div>`;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function parseMN(s) {
|
|||
|
|
const parts = s.split(',').map(x => parseInt(x.trim()));
|
|||
|
|
const m = parts[0] > 0 ? parts[0] : 3;
|
|||
|
|
const n = parts[1] > 0 ? parts[1] : 7;
|
|||
|
|
return { m, n };
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function init() {
|
|||
|
|
const sel = $('exampleSelect');
|
|||
|
|
EXAMPLES.forEach((ex, i) => {
|
|||
|
|
const o = document.createElement('option');
|
|||
|
|
o.value = i; o.textContent = ex.name;
|
|||
|
|
sel.appendChild(o);
|
|||
|
|
});
|
|||
|
|
sel.onchange = () => { $('inputArea').value = EXAMPLES[sel.value].input; build(); };
|
|||
|
|
$('applyBtn').onclick = build;
|
|||
|
|
$('inputArea').onkeydown = e => { if (e.key === 'Enter') build(); };
|
|||
|
|
build();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function build() {
|
|||
|
|
const { m, n } = parseMN($('inputArea').value);
|
|||
|
|
const steps = genSteps(m, n);
|
|||
|
|
if (controller) controller.stopAuto();
|
|||
|
|
controller = new StepController(steps, { onRender: renderStep });
|
|||
|
|
$('nextBtn').onclick = () => controller.next();
|
|||
|
|
$('prevBtn').onclick = () => controller.prev();
|
|||
|
|
$('jumpBtn').onclick = () => controller.jumpEnd();
|
|||
|
|
$('resetBtn').onclick = () => controller.reset();
|
|||
|
|
$('autoBtn').onclick = () => { if (controller.autoTimer) controller.stopAuto(); else controller.startAuto(); };
|
|||
|
|
controller.next();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
if (document.readyState === 'loading') document.addEventListener('DOMContentLoaded', init);
|
|||
|
|
else init();
|
|||
|
|
})()</script>
|
|||
|
|
</body></html>
|