2011-12-20から1日間の記事一覧
P8XCoinChangeAnotherans[]を辞書順最小の解、ans[i]≧2とすると、j≧i+2についてans[j]=0。なぜならば、ans[j]>0となるjが存在したとすると、ans[i]-=2, ans[i+1]+=1, ans[j-1]+=2, ans[j]-=1として、より辞書順の小さい解が作れてしまう。すなわち、ansの中…
P8XCoinChangeAnotherans[]を辞書順最小の解、ans[i]≧2とすると、j≧i+2についてans[j]=0。なぜならば、ans[j]>0となるjが存在したとすると、ans[i]-=2, ans[i+1]+=1, ans[j-1]+=2, ans[j]-=1として、より辞書順の小さい解が作れてしまう。すなわち、ansの中…