LeetCode 279 - 完全平方数可视化

这是一个使用 TypeScript + React + D3.js 构建的单屏幕应用，用于可视化演示 LeetCode 279 题（完全平方数）的动态规划算法过程。

功能特性

• 🎯 动态规划可视化：逐步展示 DP 数组的填充过程
• 🔄 转移过程演示：清晰展示每个状态如何从之前的状态转移而来
• 🎬 交互式播放：支持逐步播放、暂停、前进/后退
• 📊 最优解路径：在最后一步显示最优解的完整路径
• 🎨 美观的 UI：现代化的界面设计，易于理解

算法说明

问题描述

给定一个整数 n，返回和为 n 的完全平方数的最少数量。

动态规划思路

1. 状态定义：dp[i] 表示和为 i 的完全平方数的最少数量

2. 状态转移方程：

   dp[i] = min(dp[i], dp[i - j*j] + 1)
   其中 j*j <= i
   

3. 初始状态：dp[0] = 0

4. 计算顺序：从 1 到 n 依次计算每个 dp[i]

示例

• n = 12：12 = 4 + 4 + 4（需要 3 个完全平方数）
• n = 13：13 = 4 + 9（需要 2 个完全平方数）

安装和运行

# 安装依赖
npm install

# 启动开发服务器
npm run dev

# 构建生产版本
npm run build

# 预览生产版本
npm run preview

技术栈

• React 18：UI 框架
• TypeScript：类型安全
• D3.js：数据可视化
• Vite：构建工具

项目结构

├── src/
│   ├── components/
│   │   ├── Visualization.tsx    # D3.js 可视化组件
│   │   └── Visualization.css
│   ├── algorithm.ts              # DP 算法实现
│   ├── App.tsx                   # 主应用组件
│   ├── App.css
│   ├── main.tsx                  # 入口文件
│   └── index.css                 # 全局样式
├── index.html
├── package.json
├── tsconfig.json
└── vite.config.ts

使用说明

1. 在输入框中输入一个整数 n（1 ≤ n ≤ 100）
2. 点击"播放"按钮自动播放算法过程，或使用"上一步"/"下一步"手动控制
3. 观察 DP 数组的填充过程和状态转移关系
4. 在最后一步查看最优解的完整路径

License

MIT