#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int get(int x){
        int t = 0;
        while(x>0)
        {
            t+=x%10;
            x/=10;
        }
        return t;
    }
    int movingCount(int m, int n, int k) {
        //深度
        vector<vector<bool>> bb(101,vector<bool>(101,false));

        queue<pair<int,int>> que; //每个节点进入，访问与之相关的节点
        que.push({0,0});
        int dx[2] = {0,1};
        int dy[2] = {1,0};
        bb[0][0] = true;
        int ans = 1;
        while(!que.empty())
        {
            auto t = que.front();
            que.pop();
            int x = t.first;
            int y = t.second;
            for(int i = 0;i<2;i++)
            {
                int _x = x + dx[i];
                int _y = y + dy[i];
                int count = get(_x)+get(_y);
                if(_x>=0&&_x<m&&_y>=0&&_y<n&&!bb[_x][_y]&&count<=k)
                {
                    ans++;
                    que.push({_x,_y});
                    bb[_x][_y] = true;
                }
            }
        }
        return ans;
    }
};
class Solution {
public:
    int cuttingRope(int n) {
        //动态规划
        // 绳子可以分成 ij 段 cou = i* j d[c] = d[i] * j 
        //绳子 一开始不能分
        vector<int> dp(n+1);
        dp[2] = 1; // 1 1 
        for(int i = 3;i<=n;i++) //遍历
        {
            for(int j = 1;j<i;j++) //遍历 寻找最大的dp[i]
            {
                dp[i] = max(dp[i],max(j*(i-j),dp[j]*(i-j))); //每一次获得最大的dp[i]
            }
        }
        return dp[n];
    }
};
int main()
{
    int a,b;
    return 0;
}